Ken,
The chapter "Nios II Core Implementation Details" in the Nios II Processor Reference Handbook contains detailed information on cycles-per-instruction and how each core gets implemented in different FPGA families. Have a look.
http://www/literature/hb/nios2/n2cpu_nii51016.pdf (
http://www/literature/hb/nios2/n2cpu_nii51016.pdf)
Also note: As mentioned in another thread, the next release of the Nios II processor will include an option to build the multiply circuitry out of LEs in Cyclone FPGAs, which don't contain DSP blocks. This will allow Nios II on Cyclone to achieve the same multiply in very few clocks, just like on Stratix and Stratix II, at the expense of a few LEs.
Matthew