Interrupt service routines should always do the absolute minimum. Remember that while your MCU is servicing an interrupt, it is doing nothing else.
For a simple quadrature encoder, it should be possible to have a pair of ISR's, one triggered by a change on the A channel, the other triggered by a change on the B channel.
Pretty much the only thing these ISRs should do is identify whether that change means the position variable should be incremented or decremented, then update the position and end the ISR and possibly update a state transition time (if you are using this information to better estimate velocity†).
† See Velocity and acceleration estimation for optical incremental encoders by R.J.E. Merry, M.J.G. van de Molengraft, M. Steinbuch
With a pair of standard quadrature encoders, 48 transition changes per rotation and a maximum of 400RPM, your cross channel interrupts shouldn't be more frequent than 640 times a second, which should be well within the capability of a 16MHz processor.
An individual channel may produce more interrupts more frequently than that (for instance when the detector is sat on the edge) but missing those state changes does not have to affect the final position value, and there will always be a clear 1.5ms between that channel stabilising and the other channel activating.
So, as long as you can service every A/B and B/A transition, it doesn't matter if you occasionally fail to process an A/A or B/B transition as long as the state of both A and B is taken into account at the next A/B or B/A transition.
Note that if you don't need to calculate the time for your A-B and B-A transition (to calculate velocity more responsively with low resolution encoders) then you would probably be batter off having a fixed 640Hz/1.5ms timer based interrupt service routine that looks at both A and B channels, as suggested by Tim Wescott.