Surfaces and interfaces offer new possibilities for tailoring the many-body interactions that dominate the electrical and thermal properties of transition metal oxides(1-4). Here, we use the prototypical two-dimensional electron liquid (2DEL) at the SrTiO3(001) surface(5-7) to reveal a remarkably complex evolution of electron-phonon coupling with the tunable carrier density of this system. At low density, where superconductivity is found in the analogous 2DEL at the LaAlO3/SrTiO3 interface(8-13), our angle-resolved photoemission data show replica bands separated by 100 meV from the main bands. This is a hallmark of a coherent polaronic liquid and implies long-range coupling to a single longitudinal optical phonon branch. In the overdoped regime the preferential coupling to this branch decreases and the 2DEL undergoes a crossover to a more conventional metallic state with weaker short-range electron-phonon interaction. These results place constraints on the theoretical description of superconductivity and allow a unified understanding of the transport properties in SrTiO3-based 2DELs.