In wireless cellular networks with densely deployed base stations, knowing the velocities of mobile devices is a key to avoid call drops and improve the quality of service to the user equipments (UEs). A simple and efficient way to estimate a UE's velocity is by counting the number of handovers made by the UE during a predefined time window. Indeed, handover-count based mobility state detection has been standardized since Long Term Evolution (LTE) Release-8 specifications. The increasing density of small cells in wireless networks can help in accurate estimation of velocity and mobility state of a UE. In this paper, we model densely deployed small cells using stochastic geometry, and then analyze the statistics of the number of handovers as a function of UE velocity, small-cell density, and handover count measurement time window. Using these statistics, we derive approximations to the Cramer-Rao lower bound (CRLB) for the velocity estimate of a UE. Also, we determine a minimum variance unbiased (MVU) velocity estimator whose variance tightly matches with the CRLB. Using this velocity estimator, we formulate the problem of detecting the mobility state of a UE as low, medium, or high-mobility, as in LTE specifications. Subsequently, we derive the probability of correctly detecting the mobility state of a UE. Finally, we evaluate the accuracy of the velocity estimator under more realistic scenarios such as clustered deployment of small cells, random way point (RWP) mobility model for UEs, and variable UE velocity. Our analysis shows that the accuracy of velocity estimation and mobility state detection increases with increasing small cell density and with increasing handover count measurement time window.