Did I get something wrong or could you just use a PWM timer?
Like CTC or Fast PWM mode (see datasheet page 136)
You can get frequencies up to 16Mhz/2 = 8Mhz, means pulses with 0.125µs and you have no software that has to be executed, cause the timers are hardware-implemented.
I hope this helps 
DaDrivel