Encoder PPR Required Resolution
I answered a similar question regarding optical encoder accuracy here:
PWM accuracy vs speed control accuracy
Minimum resolvable angle:
\begin{equation}
\theta(1) = \frac{360}{4000}=0.09deg\\
\end{equation}
Sampling Period:
\begin{equation}
T=0.001s
\end{equation}
Expected error bounds:
\begin{equation}
\omega_{error} = \frac{\theta(1)}{T} = \frac{0.09}{0.001} = 90 \frac{deg}{s} = 15 rpm
\end{equation}
This is what you calculated. It is up to you to decide if 15 rpm is an acceptable error. One suggestion is that I would look at the mechanical dynamics of you motor and load and determine the inertia of your system. You can model the inertia as a first order transfer function and see how fast any torque disturbance will change the speed.  From there you can evaluate your sampling time to see if you really need 1 ms. Cause it is easier changing the sampling time than finding a new encoder.