Those pulse speeds are indeed nothing for an Arduino. My water flow sensors put out 500-1000 pulses a second, no problem. May not even need interrupts for that as it has a 50% duty cycle, but with all the other stuff going on it makes it a lot easier.
I've timed pulses of 3-4 microseconds in length on a 20 MHz ATtiny (to get a bit better resolution than on 16 MHz).
I've counted up to 1.4 MHz worth of pulses on a 12 MHz ATtiny, albeit not using interrupts but using a counter. That way you should be able to get to 1/2 the clock speed, so up to 8 MHz on a 16 MHz Arduino.
With interrupts you don't even have to worry about loop() taking too long to go around for every single pulse. You just need your code to take into account that there may have been multiple pulses. The newWheelPulse flag is also not strictly necessary as you can check for a change in pulse count instead.