Graphene phonons are measured as a function of electron doping via the addition of potassium adatoms. In the low doping regime, the in-plane carbon G-peak hardens and narrows with increasing doping, analogous to the trend seen in graphene doped via the field-effect. At high dopings, beyond those accessible by the field-effect, the G-peak strongly softens and broadens. This is interpreted as a dynamic, non-adiabatic renormalization of the phonon self-energy. At dopings between the light and heavily doped regimes, we find a robust inhomogeneous phase where the potassium coverage is segregated into regions of high and low density. The phonon energies, linewidths and tunability are remarkably similar for 1-4 layer graphene, but significantly different to doped bulk graphite.