I would not use an FPGA.
You mention you have no experience with FPGA's, and yet you are interested in doing digital signal processing on an FPGA... numerical manipulation + signal processing are difficult enough to get right on a computer/DSP/microprocessor, where the programming tools are conventional programming. It seems to me that using a digital signal processing project for a first FPGA project is likely a recipe for frustration.
If you want to learn FPGAs, try doing something more suited to the development tools, like state machines or communications packet processing.
For a DSP project like what you've described, I'd recommend a DSP or a Cypress PSOC or an Analog Devices Microconverter (=microcontroller with ADC+DAC builtin) instead.
(full disclosure, which provides some context for my advice: I do not use FPGAs myself. I have used programmable logic = PLDs on rare occasions. My officemate does use FPGAs frequently, and I've seen enough VHDL/Verilog code looking over his shoulder to know that it is well suited for bit manipulations. He is a seasoned engineer with lots of experience with FPGAs; in a recent conversation with him where he was doing some fairly simple math on integers with different bit widths, I told him he needed to do sign-extending on the shorter bit width number in order to subtract it properly, and he got this look on his face, like "oh man, I don't want to have to do sign extension..." Adding and subtracting is not very hard in an FPGA. Beyond addition and subtraction, you really need to know the tools and libraries. And floating-point processing??!?!!??!?!!?)
In terms of interfacing to the camera and clocking data in, that will be fine it can handle it. It may not handle the speeds you are interested in.
5MP * 3 (colours, RGB) * 15 (times per second) = 225*e6. (assuming 24 bit colour depth)
So that means you will need a clock speed of at least 225 MHz assuming you can move data on every clock signal, which you may not, depending on the sensor, so you may need to double this figure to circa 450-500 MHz
The Spartan you are looking at has a clock signal of 50MHz.
So the short answer is no, not at those speeds.
The other consideration you need to apply is how many logic blocks does your logic require? to work this out, write out your implementation in VHDL/verilog, simulate and then synthese. Read the outputs from the tool and it will tell you how many logic blocks you need, then select an appropriate FPGA which has 50% more logic blocks to allow for unuseable blocks due to routing constraints and gives you some room to grow.
Also you need to consider RAM or some other sort of memory and how your will store these bursts. If you are shooting at 15 fps for 1 second then you need 225 MB which is a lot or RAM for an embedded system.
After storing in RAM you will need to flush into ROM of some sort (for example compact flash).
Best Answer
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.