We report the results of a detailed study of surface relaxation of Hg-199 nuclear spins in paraffin coated cells. From measurements of the magnetic field and temperature dependence of the spin relaxation rates we determine the correlation time for magnetic fluctuations and the surface adsorption energy. The data indicate that surface relaxation is caused by dipolar coupling to paramagnetic sites on the surface. We also observe changes in the spin relaxation rate caused by ultraviolet radiation resonant with the 254 nm transition in Hg. (C) 2004 American Institute of Physics.