Electronic – Benchtop Frequency Counter – what does the AC specification mean

_delay_ms() is a very unprecise function, besides it takes precessor time to call it and return back.

There are many ways you could use atmega's peripherals to measure frequency, if you want to go by feeding input frequency to T1, I would suggest using another timer to measure time. You could set up and start both timers simultaneously, then catch overflow interrupt of "time" timer which will happen exactly after 256*prescaler system clock ticks, then do your math.

On another note, I would suggest you to increase your processor clock frequency as 500KHz is only 2 times less than 1MHz (Nyquist theorem), that is enough, but you will not get much accuracy at the high end.

I think what you are looking for is a phase-frequency detector (PFD). These circuits are quite often used in phase-locked-loops (PLLs) for producing a "clean" reference signal that is locked-on to a fairly noisy (or modulated) input signal. The heart of the PFD can be shown in the logic diagram on the picture below (extract taken from here): -

The two outputs labelled "U" and "D" stand for up and down respectively and these two outputs can be combined with equal value resistors to produce an output voltage that represents the frequency/phase difference between two signals.

Wikipedia also provides some information about this type of circuit.

This Maxim article also shows how one can be implemented using D type flip-flops: -

How accurate would the computed delay difference be compared to the actual delay difference?

This is a difficult question to answer directly but I will say that PFD circuits, when used as the heart of a PLL, can achieve sub milli-hertz accuracy on locking an oscillator to an unknown input frequency of hundreds if not thousands of mega-hertz. Your two signals will begin in phase at some point and, due to the frequency difference between the two signals will drift to being completely out of phase - this will result in a cyclical output of the PFD which should be easily seen using an oscilloscope. Given that you then know how often the phases align, it is a trivial matter to compute what the average phase (or time delay) difference is per cycle.