You have stumbled across the fundamental problem of using an encoder to measure speed: they are not great for measuring low speeds.
Why is using an encoder to measure speed an issue?
The encoder has a certain angular resolution $\theta_r$ in radians and the number of counts detected by your digital counter $N$ is reported after a certain sampling time $\Delta t$. Your angular velocity is then determined for each sample time by:
$\omega = \frac{N\times \theta_r}{\Delta t} $
The smallest number of counts that can be recorded (other than zero counts, of course) is 1 count over the sample time. This means that your angular velocity resolution $\omega_r$ is determined as follows:
$\omega_r = \frac{\theta_r}{\Delta t}$
So lets say you try to measure a speed that is 1/4 of your resolution. Your measurement device will indicate $\omega = 0$ for $3\times\Delta t$ and then your minimum speed $\omega=\omega_r$ for $1\times \Delta t$ and repeat every ten sample time steps. For a speed that is 1/10 of your resolution it will measure zero for $9\times \Delta t$ and then $\omega_r$ for $1\times \Delta t$ and so on. See the figure below for an example when the speed is 1/10 of your speed resolution:

So how do you fix it?
My recommendation
Buy a different sensor. If you are operating an encoder near its speed resolution limit then you just won't be getting a very usable control signal. Look instead for a tachometer. A tachometer is a sensor that is specifically designed to measure speeds. There are many different varieties of this type of sensor available so it is hard to recommend a specific type without knowing more about your application. However, if you need electrical output for some kind of controller then I think your best bet would be a variable reluctance sensor tachometer or a hall effect sensor tachometer.
Otherwise
If buying a good sensor is simply not an option then, as you stated in your question, you can increase your sampling time (decrease your sampling rate) to improve your velocity resolution. The main problem with this solution is that you could increase your sampling time to the point where your system is no longer controllable, or is not controllable in a practical sense. Again, without knowing more about your application it is difficult to say what a reasonable sampling time would be. I would not suggest getting better encoder resolution because 14-bit is already very fine angular resolution.
Sources: Beckwith, Marangoni and Lienhard. Mechanical Measurements, 6th Ed.