We study the coherent dynamics of cyclotron resonance (CR) in ultrahigh-mobility two-dimensional electron gases via time-domain terahertz magneto-spectroscopy. The CR decoherence time increases with decreasing temperature but saturates below 10 K. We observe an increase in both CR decoherence rate and CR mass when holes are created via optical pumping; the latter indicates a breakdown of Kohn's theorem due to electron-hole Coulomb interactions.