(GeTe)mSb2Te3 alloys have been previously shown to be excellent thermoelectric material with figure of merit >2 when fully optimized. The (GeTe)mSb2Te3 superlattice can be visualized as m layers of GeTe inserted into the center of each Sb2Te3 slab, which expands the initial unit cell of Sb2Te3 to include long-range ordered 3D blocks with vacancies between the blocks. The (GeTe)mSb2Te3 superlattice exhibits a phase transition from rhombohedral (R-3m) to cubic rock salt (Fm-3m) at high temperature, similar to GeTe. This reversible phase transition is accompanied by abrupt changes in electrical and optical properties, enabling applications in phase-change memory devices. However, even though the structural and thermal properties of these materials have been studied in some depth, the effect of the phase transition on bond strength and phonon transport properties has not been studied. In this study, we combine high temperature X-ray diffraction and high-temperature resonant ultrasound spectroscopy to measure the lattice parameters, elastic moduli and sound velocity in (GeTe)mSb2Te3. We find that the elastic moduli and speed of sound increase gradually with increasing temperature up to the phase transition, then exhibit a final sharp increase upon transforming to the rock salt structure after which the elastic moduli begin to decrease. Our results suggest that with increasing temperature, the ordered vacancy layers diffuse gradually into the surrounding distorted rock salt matrix, increasing the interlayer bond strength, thus leading to the anomalous temperature-dependence of the thermal conductivity.