How do you research to find character names? Especially when it's long ago, not European, and the culture was totally different from what the region has now. For example, how would you generate names for a story set in Ancient Egyptian era (of course I can't use Arabic names)? Would you use king or nobility names (because they are available in encyclopedias etc.) for commoners?
You need to do a lot of research if you're going to write a convincing historical novel. Part of that research ought to introduce you to common names from the period. But your question might well have been rephrased as "How do you get the details right in historical fiction?" And the answer to that as well is: research.
Authors of good historical fiction typically could write decent histories of the period their fiction covers. It would not be uncommon for them to read dozens of books on the period before producing a single word of their own.
For example, here's an excerpt from a blog entry by Linda Proud, talking about the historical novelist Mary Renault:
She wrote the book from research in contemporary sources such as the histories of Thucydides, transforming the facts in the crucible of her imagination: no ordinary imagination, not the kind which pleasantly daydreams and orchestrates conversations between the famous dead, but the kind which time-travels and can experience, as if through the senses, what it is like to be someone else, in another place, another culture, another time. Mary takes us there and we become her characters.
Here is Proud giving advice to other would-be writers of historical fiction:
You do have to get the customs and technological details right, though. Did people use forks yet while dining? What type of head covering would your heroine have worn? Details like this can be maddening to research, because most historians focus on political structures and on changing religious and philosophical beliefs. The Historical Novelists Center has articles and bibliographies of sources that offer a starting point in researching for the type of information historical novelists need to place their characters in an authentic day-to-day physical setting.
And here is a link to Elizabeth Crook's Seven Rules for Writing Historical Fiction, which are well worth reading. An excerpt:
Historical novels usually take several years to write, as they require research at every turn. You won’t always be able to anticipate what you’ll need to know for a scene, and will constantly have to be returning to your references. This is entirely different from writing contemporary fiction.
Take, for example, in my part of the world, a trip from Austin, Texas to the nearby town of San Marcos. If you are going to write a present-day scene in which your character makes this trip, you will simply need to put him into a vehicle -- a pickup, or a Volvo -- and head him south for forty minutes on the flat terrain of interstate 35, passing strip malls and fields and the town of Buda. He will then take the exit marked “Wonder World”, named for a local cave and visitor’s center, and arrive in San Marcos. The only research needed to write this scene will be to drive the route yourself.
But if your character takes this journey in 1906, you will have to learn a few things before starting him out, and learn more things along the way. First of all, you need to know where the road is, and what’s on either side of it, and what kind of conveyance your character is driving. If it’s a flatbed wagon, what’s pulling it -- a horse, a half-lame mule, two mules? How often do mules need water? How much traffic will there be? Any cars? What kind of food or luggage do you have along? And what if a wheel breaks, and you have to fix it, and you cut yourself with a rusty tool -- how do you disinfect the cut? Do you even know about disinfection? When did people figure out where tetanus came from? And -- assuming that you eventually make it to San Marcos, what’s in San Marcos, anyway? As for the Wonder World exit -- when was the cave called “Wonder Cave” actually discovered?
Oh, did I mention research yet?
My first thought would be to try to find any written records or any studies done of the time period in question. There are tombs with hieroglyphics. How much has been translated? Are there any common names among those records?
From there I would look for academics, librarians, museum staff, and archaeologists who study the time period and actually contact them, and ask them this question.