Timer Problem

Hi,
have a problem with my ArduinoUNO. I would like to measure frequency of a oscillator. Therefore i use two timers, the first counts all rising edges the other interupts the first timer all 0.5 ms. Hence i achieve a number of rising edges in this time frame.
Until now i thought that the timers are able to detect signals up to 16Mhz (maybe a little bit lower because of detection errors) ... because of the clockspeed of the Arduino?!

My problem:
My measurment setup runs perfect until the oszillator reaches a frequncy around 9Mhz. Over this frequency i get some strange values. For my project i wish to measure frequncies around 40-60Mhz.

My Question:
Does the clockspeed correspond to the timer speeds? Would my problem be solved with a ArduinoDue (84Mhz)?

Kind regards
Kohlmeise