For sure 'Invariance Theory' would have been a better name.
The Einstein papers project is set up to be the definitive source of historical information.
The content is available online, and, by the looks of it, has been indexed by Google (and presumably other search engines too).
For search engine search one can use:
invariantentheorie site:einsteinpapers.press.princeton.edu
The Einstein papers project website itself has a search field too, which is what I used just now. I used the german word, as in german it is a single word.
The search term 'invariantentheorie' gives multiple locations, but not all are about physics. It appears 'invariantentheorie' is also a name for a specific area of mathematics.
This one seems the strongest candidate:
From a letter to Eberhard Zschimmer september 30, 1921
Sehr geehrter Herr Kollege! Zunächst versichere ich Sie, dass ich von
Herrn Norbert Einstein in keiner Weise gezupft worden bin. Nun zum
Namen Relativitäts-Theorie. Ich gebe zu, dass dieser nicht glücklich
ist und zu philosophischen Missverständnissen Anlass gegeben hat. Der
Name Invarianz-Theorie würde die Forschungsmethode der Theorie
bezeichnen, leider aber nicht den materiellen Inhalt der Theorie
(Konstanz der Lichtgeschwindigkeit, Wesensgleichheit von Trägheit und
Schwere). Trotzdem wäre die von Ihnen vorgeschlagene Bezeichnung
vielleicht besser, ich glaube aber, dass es Verwirrung anrichten
würde, den allgemein akzeptierten Namen nachträglich zu verändern.
It seems to me this letter is not enough evidence one way or the other. It could be, for instance, that Einstein was just being gracious in writing to Zschimmer that maybe the name 'Invarianz-Theorie' would have been better.
(I translated the letter: scroll to the end of this answer)
The search found this location because in the (english) commentary it is noted that Felix Klein had proposed 'invariententheorie'. That is how the search found that; the actual letter has the expression 'invarianz-Theorie'.
Doing additional search, with variations, is worth a try, by the looks of it.
I noticed an expression 'Minkowskischen invariantentheorie', which presumably refers to the invariant spacetime interval. This was in the course of a series of 4 lectures, delivered in 1922.
Additional historical information:
Volume 2 of the Einstein Collected Papers Project presents Einstein's scientific publications from 1900 to 1909
In the paragraph below ( page 254 ) the editors discuss some history of naming. While volume 2 covers the years 1900-1909, they look ahead to 1915, mentioning that it was only then that Einstein started using the expression 'special theory' so as to differentiate it from 'general theory'. They do mention that in 1910 Felix Klein proposed the name 'invariance theory', but the editors give no indication that at the time Einstein was aware of that proposal, or that Einstein had independently thought of that as a possible name.
The editors write:
Strictly speaking, it is anachronistic to use the term "the theory of
relativity" in discussing Einstein's first papers on the subject. In
them he referred to the "principle of relativity" ("Prinzip der
Relativität" or "Relativitätsprinzip"). Max Planck used the term
"Relativtheorie" in 1906 to describe the Lorentz-Einstein equations of
motion for the electron, and this expression continued to be used from
time to time for several years. Bucherer seems to have been the first
person to use the term "Relativitätstheorie" in the discussion
following Planck's lecture. The term was used in an article by
Ehrenfest and adopted by Einstein in 1907, in his reply. Although
Einstein used the term from time to time thereafter, for several years
he continued to employ "Relativitätsprinzip" in the titles of his
articles. In 1910 the mathematician Felix Klein suggested the name
"Invariantentheorie," but this suggestion does not seem to have been
adopted by any physicist. In 1915 Einstein started to refer to his
earlier work as "the special theory of relativity" ("die spezielle
Relativitätstheorie") to contrast it with his later "general theory"
("allgemeine Theorie"). In Einstein 1907j (Doc. 47) he does refer to
the need for generalizing the "principle of relativity" in order to
include gravitation in the theory, but throughout the present volume
the phrase "the theory of relativity" is used to denote the special
theory.
Translation of the letter to Eberhard Zschimmer.
Note: since Einstein refers to 'equality of gravity and inertia' he must have the general theory in mind.
"Now to the name relativity theory. I admit that it is unfortunate and has given rise to philosophical misunderstandings. The name invariance theory would describe the research method of theory, but unfortunately not the material content of the theory (constancy of the speed of light, equality of inertia and gravity). Still, the term you suggested might be better, but I think it would be confusing to change the commonly accepted name later."
About naming:
While 'Invariance theory' would be better for the special theory, it is, it seems to me, a poor fit for the general theory.
Newtonian dynamics is a theory of motion.
Invariance theory is a theory of motion.
The general theory is a unification of two kinds of theory: theory of motion and theory of gravity.
