Accurate 100Hz-10kHz frequency read on Arduino Mega

I'm trying to create a program for an Arduino Mega that can read a digital signal from 100 Hz-10kHz with very minimal error. My issue is that while I can read signals from 100Hz-1kHz with only 1-2 Hz error, I get up to 40Hz error when I get to 10kHz. Maybe that's all that can be expected?

Currently I do not have an oscilloscope to test with so I am using a UNO to create one. I am outputting a frequency to the Mega from the UNO's Pin 3 to the Mega's Pin 18(Interrupt 5)and connecting them together using GND as well.

The UNO generates a frequency using tone().

void setup () 
  {
    tone(3, 1000); //1kHz
  }

void loop()
{}

I believe tone() can't generate just any frequency, so I use the tables provided by Nick Gammon to make sure I'm using a frequency the UNO can generate. I have also confirmed tone() accuracy by using his code to create a frequency manually.

const byte OUTPUT_PIN = 3;  // Timer 2 "B" output: OC2B

const byte n = 249;  //1 kHz

void setup() 
 {
  pinMode (OUTPUT_PIN, OUTPUT);

  TCCR2A = bit (WGM20) | bit (WGM21) | bit (COM2B1); // fast PWM, clear OC2A on compare
  TCCR2B = bit (WGM22) | bit (CS22);         // fast PWM, prescaler of 64
  OCR2A =  n;                                // from table  
  OCR2B = ((n + 1) / 2) - 1;                 // 50% duty cycle
  }  // end of setup

void loop() { }

I have tried many different programs to read frequency. I need one that can accept frequencies on multiple pins. They don't have to all be reading at the same time, but it needs to be wired so I can read at least 4 different inputs at different times. The Mega had 6 interrupts so that would be sufficient.

Here is the program I'm using on the Mega using interrupt 5.

 // Working Values
 unsigned long  duration         =  0;      // Time of last valid action for frequency patterns
 unsigned long  temp             =  0;      // Temporariy variable for holding count for frequency measurement,
 unsigned long  last             =  0;      // Used variable for holding count for frequency measurement,

 // Interrupt Values
 volatile unsigned long count    =  0;      // Volitile variable for counting pulses for frequency measurement,  
 
 // Pin Definitions
 #define       COUNT                18       // Pin 18, INT 5  - Pulse counting input

 
 /*                                               Setup                                                   */
/*IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII*/

void setup() {
 // Set Device I/O Pinmodes
  pinMode(COUNT,  INPUT);
  
  Serial.begin(115200); 
}

/*-------------------------------------------------------------------------------------------------------*/

void loop() {
  hz();
}
 // interupt routine for pulse counting
void pulse() { 
  count++;                                   // increment count for every pulse
}
 // for counting frequency
void hz() {
  count = 0;                                    // Reset count for current loop
  duration = micros();
  attachInterrupt(5, pulse, RISING);           // Set up interrupt for counting on int 5

  while(1) {
      if (micros() - duration >=1000000 ) {     // 1 second gate time increased to correct for lcd loop
        duration = micros();                    // sets duration to current time, resetting the if statement
        temp = count; 
        Serial.println((count - last)); // Hz
        last = temp;                           // updates last to current count
        
      }
  }
  detachInterrupt(0);                           // removes the interrupt as its no longer needed
}

Again, as the Hz increases, the accuracy decreases. I believe this is due to overhead?

500 Hz: ~1 Hz error
1000 Hz: ~ 2 Hz error
2000 Hz: ~5 Hz error
5000 Hz: ~25 Hz error
10000 Hz: ~40 Hz error
25000 Hz: ~190 Hz error
40000 Hz: ~308 Hz error
64000 Hz: ~494 Hz error

These vales are just random enough that I don't think I can develop an accurate equation to adjust for this error given a certain Hz.

My question is can you see anything I'm doing wrong? Maybe the frequency I'm creating isn't accurate at higher Hz? Maybe the Mega can't use interrupts accurately after 1Khz, but there's a way to adjust for this? Maybe there's a better program to use altogether? I welcome any suggestions.