A proto-Cards Across was described as “The Strange Subtraction” in R.P.'s Ein Spiel Karten, 1853, p. 55 of the Pieper translation. In it, a spectator held a packet of cards she counted herself, and is then asked how many cards she wants added to it. Upon recounting, she has that many more cards. It's essentially one half of the modern Cards Across effect. A similar routine can also be found in Jean-Nicholas Ponsin's La Nouvelle Magie Blanche Dévoilée, 1853, p. 106 of this edition, under the title “La multiplication des cartes dans les mains d'une personne”. This trick has been published by Jean Hugard in an English translation in More Card Manipulation, Series 3, 1940, p. 31, as “The Multiplication of Cards While in the Someone's Hands”.
Jean Eugène Robert-Houdin later published the more contemporary two-packet version in Les Secrets de la Magie et de la Prestidigitation, 1868, p. 87 of the Hoffmann translation.
The plot itself seems to be much older, as variants have cropped up in earlier, unpublished books. It was described in the anonymous Asti Manuscript, c. 1700, p. 58 of the Pieper translation. This manuscript was translated in Gibecière, Vol. 8 No. 1, Winter 2013, p. 29-234. In the same manuscript, there are other variants, including a hybrid Cards Across / ACAAN.
For surveys on the plot, see also the article “Some Aspects of the 'Flying Cards'” by Peter Warlock in the Hoffmann Memorial Lecture, June 1953 (published as a supplement to the Magic Circular), Reinhard Müller's Escorial manuscript Flying Cards, 1984/85, as well as Paul Hallas' Across the Void, 2005.