In conventional superconductors, the electron pairing that allows superconductivity is caused by exchange of virtual phonons, which are quanta of lattice vibration. For high-transition-temperature (high-Tc) superconductors, it is far from clear that phonons are involved in the pairing at all. For example, the negligible change in Tc of optimally doped Bi2Sr2CaCu2O8 (Bi2212) upon oxygen isotope substitution (16O to 18O leads to Tc decreasing from 92 to 91 K) has often been taken to mean that phonons play an insignificant role in this material. Here we provide a detailed comparison of the electron dynamics of Bi2212 samples containing different oxygen isotopes, using angle-resolved photoemission spectroscopy. Our data show definite and strong isotope effects. Surprisingly, the effects mainly appear in broad high-energy humps, commonly referred to as "incoherent peaks". As a function of temperature and electron momentum, the magnitude of the isotope effect closely correlates with the superconducting gap - that is, the pair binding energy. We suggest that these results can be explained in a dynamic spin-Peierls picture, where the singlet pairing of electrons and the electron-lattice coupling mutually enhance each other.