Actually when one says "orbital velocity", it refers to the expectation value of kinetic energy ##\frac{p^2}{2m}## in the state given by the orbital in question. For the non-relativistic case where the Schroedinger equation simply reads as
$$\left( \frac{p^2}{2m} + V(r)\right)\psi_{nlm} = E_n \psi_{nlm}$$
it can be shown that ##\langle T \rangle_{nlm} = \langle \frac{p^2}{2m} \rangle_{nlm} = -E_n##. Using this, the orbital velocity is taken as the root-mean-square velocity in that orbital,
$$ v_{rms} = \sqrt{\langle v^2 \rangle_{nlm}} = \sqrt{ \frac{2 \langle T \rangle_{nlm} }{m} } = \frac{\alpha Z}{n}c $$
Now if the relativistic were to be taken into account, we must either add correction terms (and subsequently use perturbation method) or directly resort to the so-called Dirac equation, the former is useful when relativistic effect is not too large to be taken as a mere perturbation while the latter corresponds to the strong relativistic effect. But for this problem using perturbation method is more useful. To proceed one must first add the correction terms to the non-relativistic Schroedinger equation, there are more than one of such quantities but only one which directly pertains our problem, namely the kinetic energy correction term
$$ H_1 = -\frac{p^4}{8m^3c^2}$$
this correction term can be derived by applying some approximation to the Dirac equation. Therefore, the expectation value of the kinetic energy taking relativistic effect into account should be ##\langle T+H_1 \rangle_{nlm}##. The second term can be calculated analytically, for example in
http://quantummechanics.ucsd.edu/ph130a/130_notes/node345.html
From that link you should see that in the case of weak relativistic effect, the orbital velocity also depends on the orbital quantum number ##l## as opposed to the non-relativistic one.
