The story is usually told starting with Einstein's 1915 paper Explanation of the Perihelion Motion of Mercury from General Relativity Theory, or at least its drafts from 1913-14. It was the first triumph of general relativity. But how did Einstein zero in on Mercury in the first place?
Einstein's early work seems to be rather distant from astronomy. Special relativity grew out of classical electrodynamics, as did the photoelectric effect, the work on heat and Brownian motion is far from astronomy too. Even general relativity was driven by philosophical concerns about general covariance, etc., rather than empirical issues in astronomy. I am not sure how well the Mercury's anomaly was known at the time, but Kelvin and others did not mention it as one of the "clouds". While developing general relativity Einstein learned of tensor calculus from a geometer friend, perhaps he had an astronomer friend as well?
Who or what attracted Einstein's attention to Mercury, and when? What alerted him to the idea that Mercury's case was different from all those other cases, when a mundane explanation was involved?
Another twist is that special relativity combined with the inverse square law already causes elliptic orbits to precess. Sommerfeld knew that at least by 1916, when he refined Bohr's model of the hydrogen atom by using precessing elliptic orbits under special relativity kinematics. A calculation on Physics SE shows that this effect can account for about 7" out of 43" per century of Mercury's anomalous precession.
Was Einstein or his contemporaries aware of this effect for Mercury before 1915, and how did it reflect on special relativity if they were?
EDIT: VicAche's answer below led me to Conquering the Perihelion chapter in Kevin Brown's book Reflections on Relativity, which gives the whole story summarized below.
Einstein first mentions Mercury in a letter to Habicht in 1907:"At the moment I am working on a relativistic analysis of the law of gravitation by means of which I hope to explain the still unexplained secular changes in the perihelion of Mercury." He most likely got the idea from Mach's Science of Mechanics, which mentions "Paul Gerber alone, from the perihelial motion of Mercury, forty-one seconds in a century, finds the velocity of propagation of gravitation to be the same as that of light." This directly suggested that Mercury's anomaly, unlike many others, was relativistic.
Back in 1906 Seeliger gave an alternative solar corona explanation, which convinced many of his contemporaries, but not Einstein. And not Poincare, who mentioned in 1908 book Science and Method that special relativity already predicts an advance of 7" for Mercury’s perihelion. He further wrote (answering my second question):"This cannot be regarded as an argument in favor of the new dynamics, since we still have to seek another explanation of the greater part of the anomaly connected with Mercury, but still less can it be regarded as an argument against it." This likely confirmed the relativistic nature of the anomaly in Einstein's eyes. Einstein's original version of a new gravity theory ("Entwurf") first predicted negative precession, and then 18" instead of 45", which was one of three reasons he cited for abandoning it in favor of what we now call general relativity.
P.S. Although Mercury's is the only one featured in the story orbital anomalies are plenty, as are proposals to change the laws of gravity for them. Newton could not account for all of lunar precession, and Clairaut suggested a modification to inverse square law before discovering that the issue was not retaining enough terms in the Taylor series for the solution. The anomaly of Uranus famously led to Leverier's prediction of Neptune, and Leverier, who also discovered the anomalous precession of Mercury, suggested a new planet Vulcan to explain it.
Vulcan did not materialize by 1915, but neither did Pluto until 1930, and it was blamed for orbital anomalies of Uranus and Neptune known in Einstein's time. After the discovery it turned out that little Pluto wasn't responsible after all, a misestimation of Neptune's mass was. Also in Einstein's time there was still a known lunar anomaly, which was not resolved until 1940s, the non-uniformity of Earth's rotation was the culprit. Zodiacal cloud and another modification of inverse square law were suggested instead of Vulcan for Mercury by Newcomb. A more recent Pioneer anomaly also caused a lot of speculation about new gravity physics (MOND), but was finally traced to subtle thermal pressure. Some suggested it was responsible early on.