The exchange of adsorbed molecules with an adjacent liquid bulk phase provides a mechanism for self-diffusion and relaxation of density inhomogeneities at an interface. For systems where diffusion control develops in the bulk, we demonstrate non-Fickian relaxation of density perturbations at large wavevectors k > 1/h, where h is the slope of the equilibrium adsorption isotherm : relaxation proceeds as exp(-ckt) where the "speed" c = D/h and D is the bulk diffusivity. For long wavelengths, k < 1/h, relaxation is independent of k. The non-Fickian behavior results from the Levy walks performed by adsorbed molecules on the interface. In contrast, when "barrier-controlled" adsorption kinetics apply, relaxation times are always independent of wavelength. We have calculated the scattering function which exhibits these behaviors and is experimentally measurable using methods such as fluorescence recovery after photobleaching (FRAP). We predict that this bulk-mediated mode will frequently dominate relaxation at the liquid-solid interface and in many liquid-fluid cases will provide the primary mechanism for selfdiffusion.