Wizards sure can have some strange names, but there is still a certain logic to them. They are not simply invented out of the aether.
Muggle-born wizards, obviously, have Muggle names. In fact, the majority of wizards have fairly normal names, regardless of blood status. Names like Harry, Bob, Dean, or Fred.
Naming Seers
A Naming Seer is a professional diviner (but not necessarily a true Seer) that is hired to predict a newborn child's future and suggest an appropriate name. Naming Seers are not as common as they once were, as priorities have begun to shift from the importance of destiny to the value of forging one's own path. Still, there are many traditional wizards, particularly among the older pure-blood families, that put stock in these fortune tellers.
It is typically the more traditional pure-blood families, like the Malfoys and Blacks, that have more fanciful names, often with a certain theme to them (e.g. Blacks are usually named after stars or constellations, Malfoys often derive names from mythological monsters or villains, etc.). This isn't to say that half-bloods and less traditional pure-bloods do not have such names, but they are no more common in such cases than modern Muggle-like names.
But even those unusual names are not simply made up. They tend to have a rather "classical" sound, and they always have some root in history, mythology, language, etc. Names like Sirius, Bartemius, Ottaline, Draco, or Albus are all derivative of some other meaning (usually somehow indicative of some important trait of the character). For example:
- Sirius Black, an animagus that can turn into a large dog, is so named because Sirius is the Dog Star.
- Draco Malfoy is named for a Latin word for dragon or serpent, as he is the series' preeminent Slytherin, and displays many aggressive traits like a dragon.
- Albus Dumbledore's given name is Latin for white, a colour often associated with goodness and purity.
The same is true for surnames. Most sound just like Muggle surnames, and while many pure-blood families will try to deny it, the fact is that wizard families are all genealogically connected to Muggle families. There are some more unusual sounding surnames, such as Dumbledore, Hagrid, or Lupin, but these are the exception, and generally have a whimsical sound and a thematic feel to them.
- Dumbledore is an old word for "bumblebee", alluding to Albus Dumbledore busily flitting about the castle humming to himself.
- Lupin is derived from the Latin for wolf, referring to Remus Lupin's lycanthropy.
- Potter is a common surname in England, and refers to the occupation of making pottery, suggesting a simple, down-to-earth family.
It is best to avoid names with a "high fantasy" feel to them, be they given names or surnames. By this, we mean the sorts of names commonly found in Dungeons & Dragons settings, or even Lord of the Rings. The Potterverse has high fantasy elements, but it is a contemporary Earth setting, and ought to feel like one. Some examples of this type of name include: Redblade, Moonstalker, Grinfemmer, Elessar, Nightwind, etc.