Recent theory has demonstrated that the value of the electron-phonon coupling strength λ can be extracted directly from the thermal attenuation (Debye-Waller factor) of helium atom scattering reflectivity. This theory is here extended to multivalley semimetal systems and applied to the case of graphene on different metal substrates and graphite. It is shown that λ rapidly increases for decreasing graphene-substrate binding strength. Two different calculational models are considered which produce qualitatively similar results for the dependence of λ on binding strength. These models predict, respectively, values of λHAS = 0.89 and 0.32 for a hypothetical flat free-standing single-layer graphene with cyclic boundary conditions. The method is suitable for analysis and characterization of not only the graphene overlayers considered here, but also other layered systems such as twisted graphene bilayers.