Another source of family names was simple human
habit. Imagine someone who's come to a country where use of
family names is rare. He'll meet someone, and ask for their name. They might reply with any of the following:
I am Rahim iben Saiid iben Naruk iben Ahmed iben ... (Ad Nauseam)
My name is Ander Mac Reng
From the family Pai-Je, I am Chi-Lo.
I am Bull-Neck from the tribe of the Bear
All of which might be shortend by our hypothetical traveler to something like:
Rahim iben-Saiid
Ander MacReng
Pai-Je Chi-Lo
Bull-Neck Bear
Now, assuming the person he addressed liked the name he gave them (instead of lopping his head off for the insult) - this might become what they called themselves. I doubt this happened, but it's all too possible, seen as how lazy people were in obeying the customs of others.