Concentrated dispersions and pastes of soft particles are ubiquitous in everyday life (mayonnaise), in biology (biological fluids and tissues) and in geology (lava and mud). These materials display many fascinating bulk properties such as yield stress, shear thinning, aging and memory. In practice however, their motion is often dominated by wall slip, with dramatic effects when they move within confined smooth surfaces. Slip in soft particle pastes is dominant at low shear rates. By directly imaging the flow of pastes using video-microscopy, we show that slip is characterized by universal properties, which depend on solvent viscosity, bulk elasticity and particle size. A generic slip model based on elasto- hydrodynamic lubrication between the squeezed particles and the wall explains these properties quantitatively. Our results offer new routes to predict the bulk non-linear rheology of pastes.