I wonder if there is another way of looking at the problem?
Playing off your estimation of 512 FFT operations (64 point each) and 42k MAC operations... I presume this is what you need for one pass through the algorithm?
Now you have found an FFT core using 4 DSP units ... but how many clock cycles does it take per FFT? (throughput, not latency)? Let's say 64, or 1 cycle per point. Then you have to complete those 42k Mac operations in 64 cycles - perhaps 1k MACs per cycle, with each MAC handling 42 operations.
Now it is time to look at the rest of the algorithm in more detail : identify not MACs but higher level operations (filtering, correlation, whatever) that can be re-used. Build cores for each of these operations, with reusability (e.g. filters with different selectable coefficient sets) and soon you may find relatively few multiplexers are required between relatively large cores...
Also, is any strength reduction possible? I had some cases where multiplications in loops were required to generate quadratics (and higher). Unrolling them, I could iteratively generate them without multiplication : I was quite pleased with myself the day I built a Difference Engine on FPGA!
Without knowing the application I can't give more details but some such analysis is likely to make some major simplifications possible.
Also - since it sounds as if you don't have a definite platform in mind - consider if you can partition across multiple FPGAs ... take a look at this board or this one which offer multiple FPGAs in a convenient platform. They also have a board with 100 Spartan-3 devices...
(p.s. I was disappointed when the software guys closed this other question - I think it's at least as appropriate there)
Edit : re your edit - I think you are starting to get there. If all the multiplier inputs are either FFT outputs, or "not-filter" coefficients, you are starting to see the sort of regularity you need to exploit. One input to each multiplier connects to an FFT output, the other input to a coefficient ROM (BlockRam implemented as a constant array).
Sequencing different FFT operations through the same FFT unit will automatically sequence the FFT outputs past this multiplier. Sequencing the correct coefficients into the other MPY input is now "merely" a matter of organising the correct ROM addresses at the correct time : an organisational problem, rather than a huge headache of MUXes.
On performance : I think Dave Tweed was being needlessly pessimistic - the FFT taking n*log(n) operations, but you get to choose O(n) butterfly units and O(logN) cycles, or O(logN) units and O(n) cycles, or some other combination to suit your resource and speed goals. One such combination may make the post-FFT multiply structure much simpler than others...
I think any engineering design is handled top-down when you really look at the design process. This is not limited to digital electronics or even electronics at all.
Design of analog circuits is no different. You start out with what a circuit needs to do, then you come up with a overall strategy to solve the problem, then keep on drilling down until you get to whatever low level details your kind of design requires. For every engineering design I can think of, there are additional levels of abstraction both above and below the design. Again, analog electronics design is not different in that regard than any other engineering discipline. The same general process and existance of multiple levels of abstraction applies whether you are designing a audio amplifier, digital computer interface, the front wheel suspension of a car, or the cooling system of a nuclear power plant.
Let's use the design of a audio amplifier as a example. Higher levels above the design come to you as specifications. There is some limit above which you don't get to make choices (perform engineering design). The need may be to drive a small speaker so that someone within proximity can hear voice, like something built into a automated teller machine at a bank, or a gas pump. If you work for the ATM company, then you don't get to decide you want this to be a 300 W HiFi audio system for a theater.
Often determining the true requirements is part of doing a design. The company has decided to put a speaker in the new ATM so that it can issue voice prompts. They haven't said how many watts must go into what kind of speaker. This is your job to figure out. On the other hand, where the voice signal comes from may have already been determined and you don't get any wiggle room. All you can do is make sure that interface is clearly documented.
Once you have the requirements well decided and documented, you sit back and think of various high level ways to solve the problem. Pretty quickly, you'll narrow this down to a few alternatives, like getting a off the shelf class-D audio chip, a whole module that pretty much does everything between the source signal and the speaker, or something you design from lower level building blocks.
Good engineers don't just take the requirements at face value if they see something that might possibly be a small change externally but that could be a bigger advantage to their design. For example, you might prefer the audio came at you as digital words over SPI or something, but it is specified as line level analog. You go to the engineer that designed the circuit that produces the line level output. Perhaps you find that he actually has digital audio and is running that into a D/A because he figured that's whatever is downstream would want. Feeding digital audio to you not only saves money in his design, but also in yours.
This sort of looking at the bigger picture one or two levels up and trying to do the best for the overall system is all too rare nowadays. This is something the chief engineer of the project should be looking into too, but chief engineers are rare nowadays too. Often you get a project manager with little engineering skill, with nobody really coordinating the engineering effort between disciplines or subsystems.
Anyway, after you look at a few alternatives, you pick one going forwards. Let's say you decided that the does-all module is too expensive for the volume of this product. Your own discrete solution would work, but take more board space than it should, especially since it would be inefficient power-wise and dealing with the heat in the cramped space you have would be a real problem. So you go with the class D audio chip, except that none of the ones for the required power level can work directly with the power supplies you have available.
Now you have decomposed the overall amplifier into some power supply conversion, and the class D chip. Each of those will have details, etc. Eventually you get to a schematic of parts you can buy and put on a circuit board.
That may be the end of your design, but of course there are many levels below that. You're going to lay out the board, but you're not going to design the details of the physical board yourself and the process that will be used to make it. You specify holes and traces, and someone else makes sure that milling, drilling, plating, etc, all happen according to your spec. You buy a class D amplifier chip, but there is obviously significant design inside that block. If this is a super high volume product, then you might design a chip with a class D amplifier being just a part of it. Even then, someone else will design the silicon fabrication process so that you can simply talk in terms of transistors instead of masks and interconnects and doping levels and the like.
I don't see anything different here just because the design happens to be a analog circuit.
Best Answer
Once you start incorporating specific primitives into your design, that design is no longer portable — it is locked into the technology in which those primitives appear.
In order to simulate such a design, you need to have the manufacturer's simulation library for those primitives. Such libraries are often delivered as encrypted binary files, in order to prevent the release of proprietary information about the implementation of those primitives.
One thing that I often do when faced with the need to use such a primitive is to "wrap" the primitive in an outer module that has a more abstract interface that's specific to my application. This allows me to write a purely behavioral version for initial functional debugging, and also to find a different way to map that functionality onto a different vendor's proprietary technology.