In moire crystals formed by stacking van der Waals (vdW) materials, surprisingly diverse correlated electronic phases and optical properties can be realized by a subtle change in the twist angle. Here, we discover that phonon spectra are also renormalized in MoS$_2$ twisted bilayers, adding a new perspective to moire physics. Over a range of small twist angles, the phonon spectra evolve rapidly due to ultra-strong coupling between different phonon modes and atomic reconstructions of the moire pattern. We develop a new low-energy continuum model for phonons that overcomes the outstanding challenge of calculating properties of large moire supercells and successfully captures essential experimental observations. Remarkably, simple optical spectroscopy experiments can provide information on strain and lattice distortions in moire crystals with nanometer-size supercells. The newly developed theory promotes a comprehensive and unified understanding of structural, optical, and electronic properties of moire superlattices.