The reconstruction of the story is dealt with in the volume Descartes on Polyhedra: A Study of the "De solidorum elementis".
Long story short: while in Paris in 1675-1676, Leibniz copied a manuscript (now lost) titled Progymnasmata de solidorum elementis that Descartes had written circa 1639; the Leinbiz's manuscript (still existing; preserved in Hannover in the Niedersächsiche Landesbibliothek, with signature mark LH IV 1, 4b, ff. 1r-v, 15r) was rediscovered and published in 1860, by Foucher de Careil. In this work, Descartes stated (or rather, this is what Leinbiz read) that
Si quatuor anguli plani recti ducantur per numerum angulorum solidorum et ex producto tollantur 8 anguli recti plani, remanet aggregatum
ex omnibus angulis planis qui in superficie talis corporis solidi existunt.
If one multiplies four right angles by the number of solid angles and if one removes eight right angles from the product, one is left with the aggregate of all the plane angles that lie on the surface of that solid body.
In the same manuscript, Descartes also stated that the number of plane angles equals twice the number of
Sunt semper duplo plures anguli plani in superficie corporis solidi,
quam latera; unum enim latus semper commune est duobus faciebus.
The plane angles on the surface of a solid body are always twice as large as the sides; a single side is always common to two faces.
By combining these two statements, one can easily deduce Euler's formula, although Descartes did not make this connection (to be clear: Descartes deals only with polyhedra; while every convex polyhedron can be turned into a connected, simple, planar graph, Descartes never made this connection).
There is a critical edition with facing text and Italian translation (sorry...) of Progymnasmata de solidorum elementis, accompanied by mathematical, historical and philological notes, here.
See also What Descartes knew of mathematics in 1628 by David Rabouin, there is also a photograph of Leibniz's manuscript (the photographs of the whole manuscript are available in Exercises pour les éléments des solides: Progymnasmata de solidorum elementis: Essai en complement d'Euclide by Pierre Costabel).