Tienes bastantes ejemplos como hacer frecuencímetros por la red para ojear. Yo diría que el método que has utilizado no es el más acertado para dicha aplicación.
Para que te hagas una idea de cifras, un pin digital creo que puede teóricamente como máximo medir Frec_reloj/2 aunque se recomienda 2.5. Es decir, Arduino usa un cristal de 16 Mhz/2.5=6.4 Mhz. Esto sin hacer absolutamente nada de código, y para una señal cuadrada de 50% duty cycle. Creo recordar que era algo así las limitaciones (mejor es mirarlo en el datasheet).
Por lo que para medir 4 Mhz, te lo tienes que currar.... 
Saludos
Igor R.