We present a detailed derivation and testing of our approach to rescale the dynamics of mesoscale simulations of coarse-grained polymer melts (I. Y. Lyubimov et al. J. Chem. Phys. textbf{132}, 11876, 2010). Starting from the first-principle Liouville equation and applying the Mori-Zwanzig projection operator technique, we derive the Generalized Langevin Equations (GLE) for the coarse-grained representations of the liquid. The chosen slow variables in the projection operators define the length scale of coarse graining. Each polymer is represented at two levels of coarse-graining: monomeric as a bead-and-spring model and molecular as a soft-colloid. In the long-time regime where the center-of-mass follows Brownian motion and the internal dynamics is completely relaxed, the two descriptions must be equivalent. By enforcing this formal relation we derive from the GLEs the analytical rescaling factors to be applied to dynamical data in the coarse-grained representation to recover the monomeric description. Change in entropy and change in friction are the two corrections to be accounted for to compensate the effects of coarse-graining on the polymer dynamics. The solution of the memory functions in the coarse-grained representations provides the dynamical rescaling of the friction coefficient. The calculation of the internal degrees of freedom provides the correction of the change in entropy due to coarse-graining. The resulting rescaling formalism is a function of the coarse-grained model and thermodynamic parameters of the system simulated. The rescaled dynamics obtained from mesoscale simulations of polyethylene, represented as soft colloidal particles, by applying our rescaling approach shows a good agreement with data of translational diffusion measured experimentally and from simulations. The proposed method is used to predict self-diffusion coefficients of new polyethylene samples.