The recent discovery of high-temperature superconductivity in a single unit-cell FeSe layer grown on SrTiO₃ (STO) is stimulating intensive research efforts on exploration of the dominant mechanism. Among the various competing scenarios, strong interaction between the longitude optical (LO) phonon mode in STO and electrons in FeSe is likely to enhance superconductivity. Earlier experimental studies have shown that the LO phonon energy is ~100 meV, while the FeSe Fermi energy is only ~60 meV. Based on these observations, we propose the interfacial electron-phonon interaction to be non-adiabatic, and the associated phonon-mediated electron pairing lies between the BCS-BEC crossover regime. To capture the essential physics in this regime, an interfacial polaron picture is developed to account for the enhanced superconductivity. Specifically, by considering both the polaron-induced attraction and Coulomb repulsion between electrons on adjacent Fe sites, we obtain an effective total attractive interaction between the electrons. We also provide a quantitative estimate of the superconductivity enhancement within the interfacial polaron picture using physically realistic parameters, and discuss these results in connection with our latest experimental observations.