Das Verfahren von SprinterSB ist schon sehr gut, allerdings kriegt man dabei gerade bei niedrigen Frequenzen relativ hohe Ungenauigkeiten.
Muss die Frequenz tatsächlich bi 0 anfangen, oder reichen auch 100...200Hz ?
Wie wärs die Taktfrequenz durch einen programmierbaren Vorteiler laufen zu lassen, der je nach Frequenz zwischen 1 und 256 teilt ?
Ein fester Vorteiler ginge vermutlich auch.
Dann hast Du bei 500kHz bei einem Teilerfaktor von 256 immerhin ca. 8000 Taktzyklen für deine ISR Routine.
Der Ausgang des Vorteilers wird dann natürlich wieder an einen Interruptpin , oder was ich noch besser fände, an den ICP Pin gehängt.