How far ahead can we predict solar and lunar eclipses?
On predicting planetary orbits
A number of studies have shown that the inner solar system is chaotic, with a Lyapunov time scale of about 5 million years. This 5 million year time scale means that while one can somewhat reasonably create a planetary ephemeris (a time-based catalog of where the planets were / will be) that spans from 10 million years into the past to 10 million years into the future, going beyond that by much is essentially impossible. At a hundred million years, the position of a planet on its orbit becomes complete garbage, meaning that the uncertainties in the planetary positions exceed the orbital radii.
What one can do is forgo the idea of predicting position and instead ask only about parameters that determine the size, shape, and inclination of planetary orbits. This lets one look to secular chaos as opposed to dynamic chaos, which in turn lets attempt to answer the key question, Is the solar system stable?
The answer to this question is "not quite". The key culprit is Mercury, the most chaotic of all of the planets. One factor is its small size, which magnifies perturbations from other planets. Another factor is resonances with Jupiter and Venus. Both of these planets have multiple resonances with Mercury's eccentricity (Jupiter more so than Venus), and Venus also has multiple resonances with Mercury's inclination. These resonances spell doom for Mercury. Mercury is perched on the threshold of secular chaos, and is likely to be ejected from the solar system in a few billion years.
On predicting eclipses
The issue of chaos becomes even more extreme when trying to predict eclipses, particularly solar eclipses. The Sun, Jupiter, and Venus have marked effects on the long-term behavior of the Moon's orbit. Even more importantly, however, the Moon is receding from the Earth due to tidal interactions, and this rate is not constant. The current recession rate is about twice the average rate over the last several hundred million years. Changes in the shape and interconnectivity of the oceans drastically changes the rate at which the Moon recedes from the Earth. The melting of the ice covering Antarctica and Greenland would also significantly change the recession rate, as would the Earth entering another glaciation. Even a small change destroys the ability to make long term predictions of the Moon's orbit.
NASA developed a pair of catalogs of solar eclipses: one covering a 5,000-year period spanning from about 4000 years ago to about 1000 years into the future; the other a 10,000-year catalog of solar eclipses spanning from about 6000 years ago to about 4000 years into the future. The accuracy of these catalog degrades drastically before 3000 years ago and after 1000 years into the figure. Beyond these inner limits, the path of the eclipse over the Earth's surface becomes markedly unreliable, as does the ability to determine whether the eclipse will be partial, total, annular, or hybrid. At the outer time limits of the longer catalog, whether an eclipse did / will occur begins to become a bit dubious.
Because of the Earth's much larger shadow, predictions of lunar eclipses are a bit more reliable, but not much. The problem is that of exponential error growth, which is a characteristic of dynamically chaotic systems. Predictions of lunar eclipses more than a few tens of thousands of years into the future are more or less nonsense. The millions of years asked in the question: No.
The technique of orbital averaging once again can be of aid in determining characteristics of the Moon's orbit (but not position on the orbit). This can be augmented by geological records. Various tidal rhythmites give clues as to the paleological orbit of the Moon. A few rock formations exhibit layering that recorded the number of days in a month and the number of months in a year at the time the rock formation was created.
References
Adams, Fred C., and Gregory Laughlin. "Migration and dynamical relaxation in crowded systems of giant planets." Icarus 163.2 (2003): 290-306.
Espenak and Meeus. "Five Millennium Canon of Solar Eclipses: -1999 to +3000." NASA Technical Publication TP-2006-214141 (2006).
Espenak and Meeus. "Ten Millennium Canon of Long Solar Eclipses." Eclipse Predictions by Fred Espenak and Jean Meeus (NASA's GSFC).
Laskar, Jacques. "A numerical experiment on the chaotic behaviour of the solar system." Nature 338 (1989): 237-238.
Laskar, Jacques. "Large scale chaos and marginal stability in the solar system." Celestial Mechanics and Dynamical Astronomy 64.1-2 (1996): 115-162.
Laskar, Jacques, and Monique Gastineau. "Existence of collisional trajectories of Mercury, Mars and Venus with the Earth." Nature 459.7248 (2009): 817-819.
Lithwick, Yoram, and Yanqin Wu. "Theory of Secular Chaos and Mercury's Orbit." The Astrophysical Journal 739.1 (2011): 31.
Lithwick, Yoram, and Yanqin Wu. "Secular chaos and its application to Mercury, hot Jupiters, and the organization of planetary systems." Proceedings of the National Academy of Sciences (2013): 201308261.
Naoz, Smadar, et al. "Secular dynamics in hierarchical three-body systems." Monthly Notices of the Royal Astronomical Society (2013): stt302.
How far ahead can we predict solar and lunar eclipses?
NASA has uncertainty calculations that show how certain we are about when eclipses happen. From a back of the envelope, the eclipses will likely vary by a full day 35 thousand years from now. That said, we have eclipse seasons, so we know eclipses will continue to happen, and at roughly which time of the year.
The Moon is receding from the Earth, so total eclipses will become rarer over time. A more distant orbit is also slower, so the number of eclipses per year will also reduce over time. Eclipses will keep happening until the Sun expands as it starts dying in about 5 or 6 billion years. For a bit, they will be transits, and then we'll be inside the sun's atmosphere, and friction forces could change our orbit significantly. This all supposes that a gravitational body that isn't in the solar system (or one that is!?!) doesn't drastically change the system in some fashion.
The solar system is non-integrable and has chaos. The sun-earth-moon three-body system might be chaotic.
As pointed out in other posts, 4 billion years of orbits suggest a certain system stability.
Chaos means that for slightly different initial conditions, we get wildly varying results. In fact, the stability of the solar system helps demonstrate that gravitational systems are chaotic - if bodies flew off into deep space every time, that would be predictable. As 3 body systems go, Sun/Earth/Moon is stable.