The "staircase paradox" (or "Pythagoras paradox") name appears to be recent, so it is hard to search for it. Wolfram calls it "diagonal paradox", but that may be conflating it with a different paradox due to Leibniz, which he used to argue against the actual existence of indivisibles, see The Philosophical Assumptions Underlying Leibniz's Use of the Diagonal Paradox in 1672. The horizontal zigzag/sawtooth variant appears to be older, Lebesgue reports it from as early as 1890-s. Mathpages calls it limit paradox and Lukowski (p.13) paradox of approximation. Koch's snowflake construction (1904) uses a related idea, as does Mandelbrot's "coastline paradox", which he attributes to Richardson (1961). In 1890 Schwarz gave a construction, which can be seen as a clever 2D generalization of the sawtooth paradox, of polyhedral surfaces inscribed into a cylinder and converging to it (Schwarz lanterns), with the surface areas growing to infinity, see Surface Area and the Cylinder Area Paradox.
Friend in Numbers: fun & facts (1954), p.72 gives the sawtooth paradox under the title "the field of barley". Lakoff and Núñez in Where mathematics comes from (2000) discuss a variation with semicircles as a "classic paradox of infinity". It "shows" that $π=2$. Their version, along with the sawtooth version "showing" that $2=1$, appears in Paradoxes and Sophisms in Calculus, pp. 30-31. In 1997 there was a lively pedagogical discussion involving it in MAA journals, see On Arc Length by Barry and references therein. Barbeau in the Fallacies, Flaws, and Flimflam section of CMJ mentions the Lebesgue story that Dave Renfro is probably recalling:
"A request to the newsgroup email@example.com elicited responses from
John Conway, Roger Cooke, Mark McKinzie, and Rick Otten, who provided the
following references. L. C. Young [7, 8] quotes an anecdote from Lebesgue's book,
In the Margin of the Calculus of Variations, in which the paradox was presented as
a "joke" at the College de Beauvais."
The Young's book is Lectures on the Calculus of Variations and Optimal Control theory (1981), p.152, and he quotes Lebesgue directly (see image below):
"All my papers [on this subject] are connected with a schoolboy's 'joke.' At the College
de Beauvais, we used to show that, in a triangle, one side is equal to the sum of the other two.
Let $ABC$ be a triangle. If $A_1, B_1, C_1$ are the mid-points of its sides, we have
BA+AC = BC_1 + C_1A_1 + A_1B_1 + B_1C.
On each of the triangles $BC_1A_1, A_1B_1C$, proceed as on $ABC$. We obtain a broken line, formed of
eight segments, and equal to $BA + AC$. By continuing in this way, we obtain a sequence of
broken lines, which stray less and less from the side $BC$, and which still have as length the sum of the two other sides of our original triangle. The pupils at Beauvais concluded from this,
that the segment BC, the geometrical limit of our broken lines, had as length the sum of the
two other sides $BA + AC$. My schoolfellows saw there no more than a good joke. To me,
the argument appeared most disturbing, since I could see no difference between it and proofs
relating to the areas and surfaces of cylinders, cones, spheres, and to the length of a circumference."
Lebesgue's En marge du calcul des variations does not seem to be translated into English. It was only found after his death and published in 1963. Four of the six chapters were previously published as papers.
At the end, Lebesgue probably refers to the classical approximations of arc lengths and surface areas by the "method of exhaustion". In the calculus of variations there was active work at the time on the isoperimetric problem that raised related analytic issues. It turned out that the classical proofs, from Zenodorus to Steiner, had gaps concerning existence of limit figures. Weierstrass and Edler gave first rigorous proofs for curves in 1879 and 1882, and Schwarz for surfaces in 1890.