Transition metal oxides host a wealth of exotic phenomena ranging from charge, orbital and magnetic order to nontrivial topological phases and superconductivity. In order to translate these unique materials properties into device functionalities these materials must be doped; however, the nature of carriers and their conduction mechanism at the atomic scale remain unclear. Recent angle-resolved photoelectron spectroscopy investigations provided insight into these questions, revealing that the carriers of prototypical metal oxides undergo a transition from a polaronic liquid to a Fermi liquid regime with increasing doping. Here, by performing ab initio many-body calculations of angle-resolved photoemission spectra of titanium dioxide, we show that this transition originates from non-adiabatic polar electron-phonon coupling, and occurs when the frequency of plasma oscillations exceeds that of longitudinal-optical phonons. This finding suggests that a universal mechanism may underlie polaron formation in transition metal oxides, and provides a pathway for engineering emergent properties in quantum matter.