Cellular-connected unmanned aerial vehicles (UAVs) are expected to play a major role in various civilian and commercial applications in the future. While existing cellular networks can provide wireless coverage to UAV user equipment (UE), such legacy networks are optimized for ground users which makes it challenging to provide reliable connectivity to aerial UEs. To ensure reliable and effective mobility management for aerial UEs, estimating the velocity of cellular-connected UAVs carries critical importance. In this paper, we introduce an approximate probability mass function (PMF) of handover count (HOC) for different UAV velocities and different ground base station (GBS) densities. Afterward, we derive the Cramer-Rao lower bound (CRLB) for the velocity estimate of a UAV, and also provide a simple unbiased estimator for the UAV's velocity which depends on the GBS density and HOC measurement time. Our simulation results show that the accuracy of velocity estimation increases with the GBS density and HOC measurement window. Moreover, the velocity of commercially available UAVs can be estimated efficiently with reasonable accuracy.