Well, look at it another way: How would I name my own kids, or how would I decide on a nickname for my friends?
One (denoted as A) tends to name a person (denoted as B) based on the qualities A wants to see in B, or based on qualities already observed. We also often name B after other people/entities (denoted as C) that already exist, because we like C and wants B to be just like C. There's also people who name B as A Jr. Nicknames can also be based on something he has done.
If you are writing about a hypothetical civilisation, then you should look at names of Ethiopian society at a matching level of civilisation, though you should be aware of how much influence the outside world has on Ethiopia. Find a moment in the history of Ethiopia that matches your civilisation's technological, societal, religious and geopolitical situation best and see what names are in use.
If you are writing stories about the Homo Erectus who live in that age, however, I have a few (crude) suggestions based on the scenarios I listed. Note that there's still a long way to go before complex language evolves.
- Naming after desired qualities: Hunter-gathering is in full swing during the Lower Paleolithic. Males would likely be named after desired qualities of hunters (eg. Courage, Strong Arm) while females would likely be named after the desired qualities of domestic life (eg. Sandwich, Man Friend)
- Observed qualities: People are also frequently named after what is already seen in them, especially what they resemble as a baby (eg. Warthog, Sunflower)
- Naming after existing people/entities: There's not much in the way of religion or recorded history, so at most you'll just be naming people after other people you personally know. Of course, they can be named after non-human stuff that they like (eg. Rainbow, Giraffe, Sabertooth)
- Naming after what they have done: examples can include, for example, Shadowstalker, Tuskbreaker, Toemender...
Ok, so maybe some of those names sound weird, but it's an idea, right? Also, you can look at examples from existing hunter-gathering societies that survived into recorded history. For example, among the Iroquois, newborns are given a baby name, which are held until the rite of passage where they formally take up an adult name. In such cases, baby names are usually named after desired or observed qualities, while adult names are based on some achievement in pre-adult life or events during the trial. Also, chieftains may hold a spiritual name that is used in place of their adult names only for the duration of office, resuming the adult name after relinquishing the position. Such names could be based on rare phenomena in the natural world that prehistoric humans would attribute to the supernatural (eg. Five Moons, Fire Lake, Blue Flames, White Saber, Black Sun etc.)