Understanding the bond strength of O* and OH* intermediates to metal-oxide surfaces is key to predicting the catalytic activity in oxygen-based electrochemistry. In this work, we uncover highly non-linear trends in O* and OH* adsorption energies across the 3d, 4d and 5d series of MO2 transition-metal (TM) oxide surfaces computed within Hubbard-U corrected density functional theory (DFT+U). Investigating the electronic structure with crystal orbital Hamiltonian populations (COHP) of the relevant metal-oxygen bonds reveals that the spin-dependent coupling strength between metal-d and oxygen-2p atomic orbitals together with the extent of filling of bonding and anti-bonding orbitals are the primary contributors to the adsorption energy. Importantly, we show that the integrated COHP obtained purely from bulk calculations is a highly accurate descriptor for surface adsorption energetics that captures trends across the group 5-12 TM oxide series within 0.19-0.36 eV. Our results suggest a pathway to prediction of adsorption energies for an arbitrary metal-ligand catalyst system.