If you do not need to determine the direction of the encoders, use TMR1 in counter mode instead of a PORT.

In this case, the TMR1 as counter can work in the background while you do other things in foreground.

However, if you have to use a PORT to read the encoder (mostly for direction), then you need to make sure that there is no "Pause" in your code. Any Pause will give you missing counts since the encoder is encoding the ticks faster then the "Pause" you have. This may explain why slow speed creates no problem in your case.

Since you have LCD, you probably have a Pause to match the refresh rate.