We consider the efficient numerical solution of frictional contact problems in elasticity and present a class of nonsmooth multiscale solution methods that are well suited for massively parallel computations. The approach builds on a decomposition of the problem into nonsmooth interface processes, induced by contact and Coulomb friction, and the smooth response of the elastic bulk. Exploiting the locality of the contact and friction laws, the nonsmooth interface behaviour is separated from the bulk by means of a tailored multiscale decomposition. For this purpose, a solution-dependent multilevel basis is employed, which allows the treatment of contact constraints without regularisation. A constrained Newton-type linearisation is used to restrict the linearisation to those regions where the underlying energy functional is differentiable, while sticking contact nodes are eliminated in a consistent manner. Combining these ideas with concepts from domain decomposition, we obtain scalable nonlinear solvers that admit an efficient parallel implementation and exhibit robustness with respect to problem size, mesh refinement, and frictional parameters. For linear elasticity, the resulting methods achieve multigrid-like efficiency for large-scale frictional contact problems. We further discuss how the underlying framework can be extended to problems in nonlinear elasticity and large deformations, leading to globally convergent parallel solution strategies. The flexibility of the approach also allows for straightforward extensions to coupled problems, such as thermomechanical contact. Numerical comparisons with classical active set based methods demonstrate a significant improvement in efficiency and parallel scalability.