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 Frohlich 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.