Frege did not see himself as regimenting existing practice. He explicitly says that he developed Begriffsschrift (concept-script) because he was dissatisfied with the vagueness of natural language for the conceptual analysis of mathematics, the purpose of which was not to service practice but to remake it after exposing its logical foundations (logicist program). Notationally, Frege's version of the predicate calculus with quantifiers is sometimes described as "atrocious", and it played virtually no role in the adoption of the variable/quantifier notation. SEP's Algebra of Logic Tradition, Dipert's Peirce, Frege, the Logic of Relations, and Church's Theorem and Peckhaus's Calculus Ratiocinator vs. Characteristica Universalis? The Two Traditions in Logic, Revisited give detailed accounts of relevant developments and controversies.
Two years after Begriffsschrift, in 1881, C.S. Peirce and his student Mitchell independently introduced their version of the quantifier calculus that evolved into what we have today, the original versions of $\exists$ and $\forall$ were $\Sigma$ and $\Pi$, respectively, introduced by Peirce in 1885. It spread after being enshrined in Schröder's monumental Vorlesungen über die Algebra der Logik, the three volumes published in 1890, 1895 and 1905, and picked up by Peano and Russell, among others. Vorlesungen became the notational blueprint for Russell's Principles of Mathematics (1903), and later his with Whitehead Principia Mathematica (1910-1913). Frege's role would likely have been forgotten if Russell did not pluck him from obscurity in his promotion of logicism.
Peirce built on past work more than Frege but even he was not codifying existing practice. The use of variables as in quantifier logic was largely alien to pre-19th century mathematics, and even informal use of nested quantifiers does not really appear until the work of Dedekind and Weierstrass (one can detect some precursors to it in Gauss, Cauchy, Dirichlet and Riemann, among others, but their use is transitional from the older framework of "variable quantities"). Aristotelian logic, syllogistic, is roughly equivalent to the monadic (one-place) predicate calculus, and does not require variables, mathematical purposes met by nested quantifiers were served by iterated construction (as in Euclidean geometry) and infinitesimal/kinematic interpretations (as in calculus). For a comparison of pre and post quantifier practice see Friedman's Kant's Theory of Geometry.
The movement towards modern use originated in the rise of abstract algebra, the origins of which can perhaps be traced to Vieta, see Viète's Relevance and his Connection to Euler, and it was partly anticipated by Leibniz. However, Leibniz's logical ideas had very little influence, and much of his work remained unpublished until after they were rediscovered by others. An extension of algebra to logic was developed by Boole in The Mathematical Analysis of Logic (1847), where propositional variables were introduced, and de Morgan introduced polyadic predicates (relations) in On the syllogism, No. IV, and on the Logic of Relations (1859), thus setting the stage for quantifiers. Weierstrass's limits and Dedekind's cuts soon generated applications for them. Here is from Dipert:
"Frege, apparently in response to the negative reviews attracted by his Begriffsschrift, especially one by Schroder, wrote several essays in the early 1880s in an attempt to show how his logic was superior to traditional and Boolean logic (see Frege 1880 and 1882). He shows no appreciation of the work by De Morgan and Peirce, primarily criticizes Boole's work from a quarter century earlier, and seizes mainly on issues and faults which are controversial, even today, or from which most Booleans had retreated or were then retreating... The advantages of his elegant, rigorous theory, and the implications it had for the theory of relations, became lost in this polemic for most 19th century readers.
However, Frege's battle was not lost. His victory was merely postponed a generation. Unfortunately, the legitimate contributions of Peirce and Schröder, especially to the logic of the relations, did get lost in the ensuing fray. Neither Peirce nor Schröder had the services of such an excellent propagandist as Russell. The Peirce-Schröder calculus was portrayed as purely algebraic, without the variable-binding operators Peirce regarded as essential and to which Schröder usually resorted; its weaknesses were rhetorically exploited with the bon mot 'too complicated'; its subtlest achievements were ignored (e.g., clever theorems proven and Peirce's insights into the differences between the monadic and polyadic predicate logic); and, in a final injustice, the development of the theory of relations in Principia Mathematica owes most, especially in notation, to Schröder via the influence of Peano rather than to Frege, but it was presented without substantial acknowledgement. Alfred Tarski is one of the few logicians or historians writing in the 20th century who seems to realize the proportions of this injustice".