We study the propagation of surface waves across structured surfaces with random, localized inhomogeneities. A discrete analogue of Gurtin-Murdoch model is employed and surface elasticity, in contrast to bulk elasticity, is captured by distinct point masses and elastic constants for nearest-neighbour interactions parallel to the surface. Expressions for the surface wave reflectance and transmittance, as well as the radiative loss, are provided for every localized patch of point mass perturbation on the surface. As the main result in the article, we provide the statistics of surface wave reflectance and transmittance and the radiative loss for an ensemble of random mass perturbations, independent and identically distributed with mean zero, on the surface. In the weakly scattering regime, the mean radiative loss is found to be proportional to the size of the perturbed patch, to the variance of the mass perturbations, and to an effective parameter that depends on the continuous spectrum of the unperturbed system. In the strongly scattering regime, the mean radiative loss is found to depend on another effective parameter that depends on the continuous spectrum, but not on the variance of the mass perturbations. Numerical simulations are found in quantitative agreement with the theoretical predictions for several illustrative values of the surface structure parameters.