I'm not sure myself, but I've always thought these places were Arabic in origin, if not exactly traceable to those exact cities. Tolkien was knowledgeable, but I'm not too sure HOW knowledgeable about the era of Saba. I would have guessed he was inspired by Arabic Morocco, ie the Berbers who were the archetypical 'corsairs', and were probably the ones whom the name was first applied to. Corsairs of Umbar, after all. They were pirate raiders, and probably the most high-profile 'corsairs' in history.