If you want to use them to keep track of distance traveled and compare average speed of each motor wouldnt you need to keep a running average of the pulses? Not just check an interrupt every once and a while?
The interrupt gets the pulses, and determines whether to increment or decrement the count. No timers involved.
Keeping track of distance traveled is a matter of multiplying pulse count by distance between pulses. No timers involved.
Comparing average speed is a matter of comparing pulses per unit of time from each encoder. You need a clock for that, not a timer. The clock (the millis() function) and a timer are not the same thing.
So, I'm still failing to see the problem. Sorry.