When I first read this, Alec, I thought you had caught an epic brain fart as 500-20,000 is my RPM range. But, the 20kHz requirement is real, but the lower frequency should be 5Hz representing 500rpm - I have corrected it in the original post.
Some environments where this unit will be installed already have 0-12V PWM (pump driving) signals at up to 20kHz that tell me exactly the duty cycle that I need to know. Other cases do not, so I turn to injector pulse width and I want this one device to be able to handle both cases (and any in between).
I started working on the of a F to V chip coupled with a 4-bit ADC and even though I think it could work (progressively adding in parallel resistors and capacitors) the component count goes way up. I'm now looking - per 3v0's initial suggestion and jpanhalt's thoughts in another thread - at a PIC. That is probably going to be the way to go for low power requirement, low component count, and flexibility across a wide range of input frequencies.