According to *The Oxford Dictionary of English Christian Names* by E.G. Withycombe, the name "Alice" comes to us via the Old French "Alix", "Aaliz", "Adalis", via the Old German "Adalheidis" (which is an early form of "Adelaide"). By the 12th century the name was being latinized as "Alesia" and "Alicia" and was a very common name in England as well as France, its popularity being partly due to the influence of the literary type of "Bele Aaliz" in contemporary romances. The Curis Regis Rolls of 1219-20 give a good example of the development of the name; one woman appears there in different places as "Athelesia", "Aelesia", "Aeleis le Neweman". In England it was usually "Alys", and was in time contracted to "Alse". By the middle of the 17th century it was regarded as an old-fashioned, country name and fell into general disuse, until its revival in the middle of the 19th century by the romance writers, often in the latinized form of "Alicia". The publication of *Alice in Wonderland* in 1865 no doubt contributed to its further popularity.
I also have a book titled *Welsh Names for Children*, which lists the Welsh equivalent of "Alice" as being "Alys" and "Alis".