The elephant question in the room is, why in the world would you want to use a 4096-step encoder on a DC motor axis? The control of the motor will never be even in the same ballpark of accuracy. The brushes energizing windings causes torque ripple, inductance of the windings limit the rate of change when you want to feedback current, and inertia prevents sudden changes in speed - all in all, if you want the motor to run at an exact speed, or feedback it to track a certain position, you are at least two orders of magnitude away from that 4096 steps per revolution.
I'd understand if that 4096 step encoder would be on the output shaft of a 1:256 reduction gear; or if you used, say, a 16-step encoder on the motor shaft (equivalent thing).
Everybody is ignoring the 500kHz pulse rate because it sounds so strange. What are you going to do with a pulse every 2 microseconds when just changing the motor current by any meaningful amount takes some 100 microseconds? I mean, this is like measuring a kettle temperature every 1ms to adjust a heating element when it takes a minute for the water to heat up by any significant amount.
Usually, the feedback loops run at something like 10% to 50% of the PWM frequency, and the PWM frequency is somewhere around 10-20kHz.
Try to run the feedbacks at 1kHz first and only if you can show a responsitivity problem, go for maybe 2kHz, still just fine on an 8-bitter; not 500kHz.
What comes to the encoder itself, hardware timers/counters are used for this. The AVR should have 16-bit counters available, but even if you must use a 8-bit counter, this already divides your 500kHz rate to around 2kHz; this would be the overflow interrupt in which you increment or decrement a software counter. At 2kHz, you can easily handle a 64-bit counter, for a total of 72 bits.