The phase noise tolerance of circular multilevel quadrature amplitude modulation (C-mQAM) constellations employing different carrier phase recovery (CPR) algorithms is studied. A differential decoding scheme and a bit mapping for this type of constellations are proposed. A novel CPR scheme for C-mQAM constellations is also presented. The particular distribution of the constellation points in a C-mQAM signal is exploited to reduce the required Nth power for the removal of the modulation component by a factor of two. Hence, the computational complexity of the proposed algorithm is drastically reduced. The combined linewidth symbol duration product (??Ts) tolerance of different CPR algorithms for C-mQAM constellations is studied and compared with the proposed CPR scheme. The results are analyzed at 3.8e-3 and 1e-2 bit error rate forward error correction limits. The proposed CPR scheme achieves similar ??Ts tolerance compared to single stage BPS algorithm while its computational complexity is reduced by group factors of 27.2 | 32.3, and 30.5 | 32.6 (in the form of multipliers | adders) for C-16QAM and C-64QAM, respectively.