We compute electron-phonon coupling (EPC) of selected phonon modes in graphene and graphite using various ab-initio methods. The inclusion of non-local exchange-correlation effects within the GW approach strongly renormalizes the square EPC of the A$'_1$ {\bf K} mode by almost 80$%$ with respect to density functional theory in the LDA and GGA approximations. Within GW, the phonon slope of the A$'_1$ {\bf K} mode is almost two times larger than in GGA and LDA, in agreement with phonon dispersions from inelastic x-ray scattering and Raman spectroscopy. The hybrid B3LYP functional overestimates the EPC at {\bf K} by about 30%. Within the Hartree-Fock approximation, the graphene structure displays an instability under a distortion following the A$'_1$ phonon at {\bf K}.