The Hebrew word for two is shnayim (shnaim) שניים. The feminine form is shtayim (shtaim) שתיים, and just like with the switch between echad and achat, we need to explain this one as well.
I have seen two explanations as to how the gender transformation developed. According to Steinberg in his Milon HaTanach, the original form was shintayim שנתים, but as we've seen before, the nun has a tendency to drop out of the middle of words.
Klein, however, writes that:
According to the opinion of several scholars, שתים is the abbreviation of אשתים. If it were really so the 'daghesh' in the ת of שתים would be accounted for. I am convinced that שתים is really the shortened form of אשתים and owes its form to the masculine equivalent שנים. I am of the opinion that אשתים is nothing but the dual form of עשתי, אשתי (=one), related to Akka. ishten (=one). אשתים as the dual of אשתי, accordingly lit. means 'two ones' (i.e. 'one taken twice'). cp. מאתים (=two hundred), אלפים (=two thousand), etc.
I have to admit that I'm not sure I follow Klein's entry, and I believe there might be a typographical error. Is he convinced that shtayim comes from eshtayim or not? If not, then perhaps he does agree with Steinberg.
The "several scholars" that he quotes likely includes Ibn Janach. According to this site, back in the 11th century, Ibn Janach noticed that shtayim is the only word in Hebrew that has a dagesh kal after a shva nach. (For more information about these terms, look at the Wikipedia article on Hebrew vowels.) He therefore concluded that the original form of the word was eshtayim, but the alef dropped off with time. (See also the Radak on Shoftim 16:28). The author of this essay (unfortunately I don't know who it is), mentions two other terms where the alef dropped off an original term, and the shva nach remained in place:
אשמורה > שמורה
אתמול > תמול
Steinberg also noticed this anomaly, but explains that because people were accustomed to saying shintayim, the dagesh remained in place.
Klein claims that shnayim derives from שנה - "to repeat", which also means "to teach". From here we get the word mishna משנה , and from the Aramaic cognate תנא - the Tanaim תנאים (the teachers of the Mishna.)
The Hebrew word for second (1/60th of a minute) - shniya שניה - is a loan translation from the Latin pars minuta secunda (= second small part of an hour).
The homonymic root שנה meaning "to change" is not related. According to Horowitz's approach, we can see this because of the transformation from Hebrew to Aramaic. Where שנה meaning "to repeat" becomes תנא, the root meaning "to change" maintains the shin. According to Klein, the word for year, שנה shana, originally meant 'change; period of changing seasons'.
And lastly, the word for sleep, shena שינה, derives from an entirely different root - ישן.