What you want is a PID (Google "Arduino PID", then read up on how PIDs work in the real world) that is controlling velocity, rather than position. You can use the FreqMeasure library to calculate the velocity using one channel of the encoder as the input signal.
Regards,
Ray L.