What helped Einstein to provide a more accurate description of gravity than Newton?
- A well-developed idea of a field theory. Newton thought of the force of gravitation to be operating with an action-at-a-distance mechanism. While this bothered him, it remained an unresolved question to him. However, by the time of Einstein, the idea of thinking of the force of gravitation in terms of a field theory had been developed.
- Lorentz invariance. While the shift from thinking of the theory of the force of gravitation in terms of a field theory was an important conceptual shift, nothing really changed in terms of the mathematical description of the force of gravitation. But, with the development of special relativity, Einstein had realized that the laws of physics should be Lorentz invariant, unlike the Newtonian law of gravitation which was Galilean invariant.
- Mass-energy equivalence. This is another aspect of the development of special relativity which was relevant to going beyond the Newtonian law of gravitation. Einstein had realized through special relativity that mass and energy are not distinct properties but are rather unified in a profound way. This led him to believe that if mass plays a role in causing gravitational attraction then so should energy. However, as I said, this is closely related to my previous point: Lorentz invariance.
- Riemannian geometry. Putting together all the physical axioms that Einstein had developed crucially required the use of Riemannian geometry. In fact, learning the tools of Riemannian geometry was the hardest part for Einstein in his journey of developing his theory of gravity.
Finally, I would like to mention that two crucial elements that went into the development of general relativity (perhaps, the most crucial two elements) were already present at the time of Newton. One of them was the equality of the inertial and the gravitational mass (something that Newton also found curious) and the other was the question of what determines which frame is an inertial frame (to which, Einstein ultimately found the answer: the freely falling frame is the inertial frame). This is not to say that Newton should've developed general relativity had he been clever enough. Lorentz invariance and non-Euclidean geometry were absolutely indispensable in the development of general relativity and they were too way ahead in the future to be discovered at the time of Newton.
Riemannian geometry, the mathematical basis for General Relativity, was unknown in Newton’s day. The only geometry available to Newton was Euclidean geometry.
In addition to all the answers listing the improved mathematical tools, I think it's important to mention the enormous progress made in astronomy, thanks to both the vastly improved manufacturing techniques that enabled telescopes far beyond anything possible in Newton's time (remember that Newton himself laid an important foundation in the then-new field by inventing the reflector telescope), and, well, the widespread use of Newtonian mechanics in developing celestial mechanics. The progress of astronomy gave an extremely important source of insight: the known problems that were encountered since Newton developed his theories. It's the kind of input that's only possible once you have your theory widely used and tested.
The perihelion shift of Mercury's orbit in particular was an important indication of success of the general relativity, being a well-known problem that both showed that classical gravity had shortcomings, and that the general relativity was on the right track in explaining it.