Determining an effective way to reduce computation complexity is an essential task for adaptive echo cancellation applications. Recently, a family of partial update (PU) adaptive algorithms has been proposed to effectively reduce computational complexity. However, because a PU algorithm updates only a portion of the weights of the adaptive filters, the rate of convergence is reduced. To address this issue, this paper proposes an enhanced switching-based variable step-size (ES-VSS) approach to the M-max PU least mean square (LMS) algorithm. The step-size is determined by the correlation between the error signals and their noise-free versions. Noise-free error signals are approximated according to the level of convergence achieved during the adaptation process. The approximation of the noise-free error signals switches among four modes, such that the resulting step-size is as close to its optimal value as possible. Simulation results show that when only a half of all taps are updated in a single iteration, the proposed method significantly enhances the convergence rate of the M-max PU LMS algorithm.