4512 interrupts per second is not an unreasonable number, provided you keep the ISR short and efficient.
Do you need the full resolution provided by the encoders, or will half the resolution be sufficient? If half the resolution is acceptable, then you can generate an interrupt on just one of the encoder outputs, instead of on both of them.