Arduino is poor in terms of calculation, and it is not made for motor control. If you need a precise velocity, then you need a MCU or DSP with QEI - Quadrature Encoder Interface. It measures frequency and period of pulse train, then uses the information of the method which is more plausible.
For motion control you would need a fast MCU, not a legacy 8-bit MCU. An integrated FPU is welcome, but not mandatory if it has enough speed.
You better find some other platform.