We study the effect of strong electron-phonon interactions on the damping of the Higgs amplitude mode in superconductors by means of non-equilibrium dynamical mean-field simulations of the Holstein model. In contrast to the BCS dynamics, we find that the damping of the Higgs mode strongly depends on the temperature, becoming faster as the systen approaches the transition temperature. The damping at low temperatures is well described by a power-law, while near the transition temperature the damping shows exponential-like behavior. We explain this crossover by a temperature-dependent quasiparticle lifetime caused by the strong electron- phonon coupling, which smears the superconducting gap edge and makes the relaxation of the Higgs mode into quasiparticles more efficient at elevated temperatures. We also reveal that the phonon dynamics can soften the Higgs mode, which results in a slower damping.