I believe potentials in Maxwell's equations were introduced originally to make solving equations simpler -- it wasn't until a bit later that the Lorentz symmetry was noticed. Similar potentials are introduced in 2D hydrodynamics as well, see e.g. stream function. So I would say that the reason for introducing these potentials originally was always to simplify the algebra.
Of course, whenever one has some nice trick like this, there's a deeper reason. Here the "deeper reason" for introducing various potentials has to do with the Helmholtz decomposition (even deeper, coming from the Hodge decomposition), which guarantees that vector fields can be written as a sum of a curl-free vector field and a divergence-free vector field. This decomposition "plays nicely" with wave equations in the sense that there are natural wave modes, transverse (divergence-free) and longitudinal (curl-free) which propagate independently. See the discussion of transverse and longitudinal, i.e. the application of the Helmholtz decomposition to a Fourier transform of a vector field, which obviously is highly applicable to the P (longitudinal) and S (transverse) waves in seismology.
Intuitively, the idea of the Helmholtz decomposition is a bit like breaking a vector into independent components, and then calculating what happens to each separately, except now one is working with vector fields.