According to the OED, the evolution for "eensy" is in fact, as Jim suggested in the comments:
tiny > teeny > teensy > eensy.
More specifically, the dating laid out in the OED offers this ordering for attestations leading up to "eensy weensy."
tiny > teeny > teeny-weeny > teensy > teensy-weensy > eeny-weeny > eensy-weensy
Tiny dates back to the sixteenth century. Teeny is first attested in the OED in 1802 in a quote that compares the two terms.
The adjective tiny, in some provinces teeny, is no doubt from this root.
- 1802 Monthly Mag. Dec. 405/1
Meanwhile, Teeny in reduplicated form as "teeny-weeny" appeared attested in 1842.
Did momor's yettle Dimmy want to put its teeny-weeny footseys in the gravy?
- 1842 Penny Satirist 22 Oct. 2/1
Teensy appeared in 1856 as a variation of teeny, and is attested in the reduplicated form that preceded "eensy weensy" as teensy-weensy in 1872.
Rose was no longer a funny teensy-weensy of an infant pig, but was now a half-grown, solid, fat porker.
- 1872 Our Young Folks July 411
Slightly later than that, and preceding "eensy-weensy," we have our first similar reduplicated variant, "eeny-weeny."
He [sc. a pet fox] was an eeny weeny cunning little red darling.
- 1894 Narka (Kansas) News 7 Sept.
Finally, in 1904, we have our first attestation of "eensy" with "teensy," but the words are separated by a comma and do not appear as an idiomatic reduplication.
He thought they'd be about six or eight little ducks... There were only two ‘eensy’, ‘weensy’ little ones.
- 1904 Churchman (Hartford, Conn.) 16 July 111/3
1935 offers our first attestation of "eensy weensy" as a reduplication, and it appears hyphenated.
Not even if they are eensy-weensy pieces?
- 1935 S. Cleugh Angel who couldn't Sing xii. 157
Interestingly, the OED also offers an outlier variant "eentsy teentsy" appearing in 1914, but this does not appear to have played an etymological role in the formation of "eensy weensy."
If he discovered one edge protruding even an eentsy-teentsy bit beyond the others it would make him unhappy.
- 1914 Daily Northwestern (Oshkosh, Wisconsin) 10 Feb. 6/5