Thank you for your hints. It is really great community here, and you really give inspiration to go forward.

I have given extensive thought about the language element. First, I started with races and people of the land. Then I used Swadesh list with words that should be common in most of the languages, and tried to fill this list linguistically sound for each main linguistic group. Of course, over the time the languages would change even inside the group, but those word would be the "root" words for place names.

The history in brief would be something like this (note that I will not use the names of people or place names, that is still WIP):

When first men came to the great northern continent over the narrow sea, many thousand years ago, they found it already inhabited. Strong, fierce and hard-working as they were, they quickly grew in numbers and started pushing to the west, over the great rivers, endless forests and great mountain ranges that were in their way. They respected the forest dwellers and traded with the kings of the mountain people, which in time helped them to build a great kingdom east of the impassable mountain ranges. But in time people of this kingdom forgotten tho old allegiances, partly maybe because they had long forgotten the old folk, now hidden in the western wilderness, and the mountain people deep in their underground cities. Many centuries the lords ruled over the fertile lands, but their old nemesis, who they fled when they crossed the sea was back. A great war was fought, and the enemy was driven back, but the great old kingdom, already weakened by infighting, fell apart. That drove many people to move further west, over the mountains.
Those people founded another kingdom, west of the great mountains, from the sea on the south, bordered by mountains and desert on the east, and great marshes on the north, cradled by the great river. This kingdom flourished again, and brought back the glory of the elder days, until the war drums sounded again...