Friction force microscopy experiments on moiré superstructures of graphene-coated platinum surfaces demonstrate that in addition to atomic stick-slip dynamics, a new dominant energy dissipation route emerges. The underlying mechanism, revealed by atomistic molecular dynamics simulations, is related to moiré ridge elastic deformations and subsequent relaxation due to the action of the pushing tip. The measured frictional velocity dependence displays two distinct regimes: (i) at low velocities, the friction force is small and nearly constant; and (ii) above some threshold, friction increases logarithmically with velocity. The threshold velocity, separating the two frictional regimes, decreases with increasing normal load and moiré superstructure period. Based on the measurements and simulation results, a phenomenological model is derived, allowing us to calculate friction under a wide range of room temperature experimental conditions (sliding velocities of 1-10⁴ nm/s and a broad range of normal loads), and providing excellent agreement with experimental observations.