FPGA Logic Gate Count
FPGA manufacturers don't use equivalent gate counts much any more, even in the hand-wavyest marketing materials. Like lines of code or megahertz of processor speed, it's a highly inaccurate metric for measuring the device capability, and in the FPGA markets the customers wised up enough to suppress its use.

To estimate the size device you need, you'll need to look at the summary on p. 2 of the datasheet you linked. Usually you can get a decent idea early on in your design process how many flip-flops, how many i/o's and how much ram your design needs. One or the other of those will typically be the critical resource that determines the size of part you need. 

If you aren't tightly cost-constrained, use a device 2x or more bigger than you think you need. It will give you room for feature creep in your design and also speeds up development because the design tools won't need to work so hard to fit your design into the available resources.

Edit, pulling in things from comments,

You mentioned that your design is mostly unclocked.

The issue with this is that FPGA design tools depend on clocking and the resulting timing constraints to drive optimization of the synthesized design. If you want to do unclocked design in an FPGA it's possible in principle, but you're not going to get much help from the tools (or vendors) and you'll probably need to find a specialized community who do that kind of thing to get any support.

In any case, you can look at the Spartan 6 Configurable Logic Block User's Guide to see what resources are available in each block. Then mentally map your design to those resource to see how many blocks you need. That should be enough to let you pick the right size device. 

For example, you can see in that document that the LX45 part contains about 27,000 6-input LUTs. Each LUT can be used to implement an arbitrary combinatorial logic with up to 6 inputs. If you can express your logic in terms of this primitive, you can estimate whether your design fits into the device.