Electron-phonon (e-ph) interactions are pervasive in condensed matter, governing phenomena such as transport, superconductivity, charge-density waves, polarons, and metal-insulator transitions. First-principles approaches enable accurate calculations of e-ph interactions in a wide range of solids. However, they remain an open challenge in correlated electron systems (CES), where density functional theory often fails to describe the ground state. Therefore reliable e-ph calculations remain out of reach for many transition metal oxides, high-temperature superconductors, Mott insulators, planetary materials, and multiferroics. Here we show first-principles calculations of e-ph interactions in CES, using the framework of Hubbard-corrected density functional theory (DFT+U) and its linear response extension (DFPT+U), which can describe the electronic structure and lattice dynamics of many CES. We showcase the accuracy of this approach for a prototypical Mott system, CoO, carrying out a detailed investigation of its e-ph interactions and electron spectral functions. While standard DFPT gives unphysically divergent and short-ranged e-ph interactions, DFPT+U is shown to remove the divergences and properly account for the long-range Fröhlich interaction, allowing us to model polaron effects in a Mott insulator. Our work establishes a broadly applicable and affordable approach for quantitative studies of e-ph interactions in CES, a novel theoretical tool to interpret experiments in this broad class of materials.