Small polaron formation in transition metal oxides, like the prototypical material rutile TiO2, remains a puzzle and a challenge to simple theoretical treatment. In our combined experimental and theoretical study, we examine this problem using Raman spectroscopy of photoexcited samples and real-time time-dependent density functional theory (RT-TDDFT), which employs Ehrenfest dynamics to couple the electronic and ionic subsystems. We observe experimentally the unexpected stiffening of the A(1g) phonon mode under UV illumination and provide a theoretical explanation for this effect. Our analysis also reveals a possible reason for the observed anomalous temperature dependence of the Hall mobility. Small polaron formation in rutile TiO2 is a strongly nonadiabatic process and is adequately described by Ehrenfest dynamics at time scales of polaron formation.