There is also the possibility of using frequency warping (also work as a magnifying glass in that you get improved resolution in your freqency range of interest for the same size FFT at the expense of lower resolution at higher frequencies). However, you don't save any MIPS as the FFT size is not reduced and the frequency warping is far from cheap.
If you only want to compute certain bins in the FFT (and thus save MIPS) there are a couple of methods to do that. For instance the sliding DFT. The references in this paper gives a very nice explanation http://www.comm.utoronto.ca/~dimitris/ece431/slidingdft.pdf. I also think the goertzel algo does something similar but I don't know it.
Then there is the option of downsampling before FFT'ing. That will probably also save some MIPS.
Edit: Just to clarify the comment regarding Goertzel algorithm not being useful. By directly plugging values into the expression found at the bottom of this wiki page http://en.wikipedia.org/wiki/Goertzel_algorithm then the Goertzel approach will be more complex than an FFT when the size of the FFT required is larger than 128 (assuming FFT size is a factor of 2 and a radix-2 implementation).
However, there are other factors that should be taken into account which goes in favor of the Goertzel. Just to cite the wiki page:
"FFT implementations and processing platforms have a significant impact on the relative performance. Some FFT implementations[9] perform internal complex-number calculations to generate coefficients on-the-fly, significantly increasing their "cost K per unit of work." FFT and DFT algorithms can use tables of pre-computed coefficient values for better numerical efficiency, but this requires more accesses to coefficient values buffered in external memory, which can lead to increased cache contention that counters some of the numerical advantage."
"Both algorithms gain approximately a factor of 2 efficiency when using real-valued rather than complex-valued input data. However, these gains are natural for the Goertzel algorithm but will not be achieved for the FFT without using certain algorithm variants specialised for transforming real-valued data."