The notation was introduced by Hamilton in 1834, who shifted the focus from the original Maupertuis-Euler version of the least action principle. The tradition followed him probably because his exposition was definitive and systematic. It is also possible that thinking of "stationary action" makes the notation "make sense" to people, although this name is much more recent, and certainly not due to Hamilton.
Neither Maupertuis in Derivation of the laws of motion and equilibrium from a metaphysical principle (1746), nor Euler in Methodus inveniendi (1744) use any letter for action. Euler simply writes $\int vds$, and Maupertuis does not even write a formula.
Hamilton in On a General Method in Dynamics (1834) uses $V$ (for "varying action"), which he calls the "characteristic function", for the Maupertuis style action (see the Scholarpedia article on the difference). But near the end he remarks:
"Before we conclude this sketch of our general method in dynamics, it will be proper to notice briefly a transformation of the characteristic function, which may be used in all applications. This transformation consists in putting, generally, $V=tH+S$, and considering the part $S$, namely, the definite integral
$\int_0^t (T+U)dt$ as a function of the initial and final coordinates and of the time..."
This $S$ is just called an "auxilliary function" and no explanation for the choice of $S$ is given. It could have been as simple as destylizing $\int$ back into $S$. In the Second Essay on a General Method in Dynamics (1835) $S$ is renamed into the "Principal Function", and takes the center stage. This is where much of familiar Hamiltonian dynamics is developed in the familiar form. Still, we get no explanation as to the choice of $S$:
"The former Essay contained a general method for reducing all the most important problems of dynamics to the study of one characteristic function, one central or radical relation. It was remarked at the close of that Essay, that many eliminations required by this method in its first conception, might be avoided by a general transformation, introducing the time explicitly into a part
$S$ of the whole characteristic function $V$; and it is now proposed to fix
the attention chiefly on this part $S$, and to call it the Principal Function. The properties of this part or function $S$, which were noticed briefly in the former Essay, are now more fully set forth; and especially its uses in questions of perturbation, in which it dispenses with many laborious and circuitous processes, and enables us to express accurately the disturbed configuration of a system by the rules of undisturbed motion, if only the initial components of velocities be changed in a suitable manner."
See The Early History of Hamilton-Jacobi Dynamics 1834-1837 by Nakane and Fraser for more details.