Funny I ran across this site. Our family name is a rare one. I am in the US Army and have been stationed in Germany, twice. My father told me the name was German decent, so I inquired when I was stationed and this is what I found..
The name itself is a latin word, literally translated as "better" or "excelling." According to a German priest I ran into, there are several Melius families south of the Danube river (where his parish was). A little more research into German history shows that the Romans of course invaded Europe about as far north as the Danube river, and to my guess, left a few of their own behind. I found out there was a Roman knight with the surname of Melius at one time, way back when.
For what it's worth. I myself, grew up in Minnesota (Twin Cities area). My grandfather's name was Fred Melius (also have an unlce in Wyoming by same name). There was another Melius "clan" also in the Twin Cities, but I don't know how closely related we are.