(Don't mix this up with the "real history" of the name "Uletha". I have no idea about that yet, or is there something written in the Wiki?)
When did the name "Uletha" come up? Already in 2010 I imagined the continent around Kalm, where the cities of Forberg (the first city I developed in Kalm) and Tarott are located. It took a while until it got its name, but it must have been at some time in summer 2010 that I found the name, together with a good friend of mine. We wanted to find a nice name, starting with a voal, but not with A or E (and yes, maybe also not O) :) and we both liked "Uletha" as a continent name. "Ulethaplatz" metro station of U7 metro line in Tarott was the first appearance of the name on the map, before the start of OGF. (See also this very old and bad quality version of the original Tarott map). Later, I called the old harbour re-development area around Ulethaplatz "Ulethastadt".
In summer 2013 I sketched the first version of the Uletha outline in OGF, and Thilo did the other continents of the old world (I liked his ones a bit more, Uletha is in some points a bit too close to "Eurasia"). Before the OGF Uletha outline sketch I only had had a very rough idea of the north-western part of the continent.
(By the way: At the time I imagined the harbour of Tarott, I also imagined the name of one of the continents of the so "new world" in OGF: Ereva and one of the harbour bassins got the name "Erevahafen". I did not name it in the OGF map yet, but you can see it on this old original Tarott map (at Q10). Later I was happy, because the name was chosen for the respective continent in an OGF continent naming competition.)
So, this is how the name developed. I just wanted to give you some details here.