Something is clearly wrong with either your code or your input signal. The Input Capture example sketch works fine at 975.56 Hz and should get to at least 100 kHz (1000 times higher than your limit). Getting to 1 MHz will be hard because that only allows 8 instruction cycles between interrupts.
What is the source of your input signals?