Max frequency that can be measured with Arduino Atmega2560
The Arduino ATMega2650 is listed as having a clock speed of 16MHz, meaning that it should be able to handle this at least in terms of instruction cycles. If you look at the datasheet (P.39) for the actual ATMega2650 chip it appears the I/O clock runs at the same speed as the CPU clock.

There is also this forum post where someone found the maximum digital write speed to be around 100kHz. 

I'd say go for it. The chip should be able to handle this. The only place you might run into issues is if you try to do too much in your 1 second timer interrupt, but if all you are doing is returning the counter value then resetting you should be fine.