Interrupts have a lot of overhead due to save/restore of context. I looked at the assembly code for an interrupt that just incremented an unsigned long and it was 29 instructions. Optimistically estimate 2 cycles for each instruction and you're looking at 59 cycles, which at 16 MHz translates to 3.625 microseconds, not including time for the AVR to actually recognize and jump to the interrupt. That means top frequency would be about 275 kHz, assuming your processor is doing nothing else but getting interrupted.
Why not just use the input capture to wait for one edge, wait for the next one, then measure the time between the two edges? No interrupts required.