As long as the quadrature counter itself has enough bits to track movement for a decent period, why not just do the speed calculation at a fixed interval based on a different timer interrupt?
You can adjust that rate to ensure you have adequate time for the calculations and sufficient delay between interrupts for the normal program functions, whatever they are.
With slow movement the calculations may be repeated faster than necessary - but you could always add a software scaling type function to only calculate one in ten, twenty five or a hundred interrupts etc. for more precise calculations at low speeds.
eg. Wait for either a certain time (number of interrupts has passed) so a new reading is required, or more than a specific movement has accumulated, before you need to re-calculate, so it automatically stretches the interval for better accuracy with low speed movement.