We develop a scalable parallel finite element solver for the elastic wave equation discretized using an implicit Newmark scheme in time on unstructured meshes. The resulting system of linear equations is solved with an additive Schwarz preconditioned Krylov subspace method. We present numerical and analytical evidence to explain the behavior of the algorithms and discuss applications to a fluid-structure interaction algorithm that implicitly couples the elasticity equation with the Navier-Stokes equations to simulate blood flow in compliant arteries.