OK, this title is taken directly from the article, but it's wrong. As the paper beneath the headline clearly states, it claims that Khoisan have been the largest effective population through history, a rather different idea. You can be the largest effective population for thousands upon thousands of years of being the smallest population in the conventional sense.
Compare the headline with a nonrandomly-chosen sentence from the paper:
Headline: Khoisan hunter-gatherers have been the largest population throughout most of modern-human demographic history.
Paper: Our hypothesis may [...] suggest that the Khoisan hunter-gatherers and their ancestors have been the largest population in terms of genetic diversity throughout modern-human history. (emphasis added)
From what I remember of my major in linguistics at UCT (I was lazy and it was almost 10 years ago):
The Khoisan languages have a greater density of phonemes (there are more identifiably different sounds) than in any other on the planet. This language [1] has 43 clicks, compared to the 3 of Xhosa and Zulu (actually it might be that by the system of measurement used in that article Xhosa/Zulu actually have more, but it still won't be as many).
Speculation: I always imagined that this was similar to the story of Mitochondrial Eve, that these languages look like what language looked like 150 000 years ago while the rest of the planet's languages are fragments, kind of like we only have fragments of Mitochondrial Eve's DNA. Of course I have no idea what the current thinking is on ME, maybe that idea has been discredited.
tl;dr the Khoisan lived in the part of Africa that kept good throught all climate changes phases. The other populations suffered reduction in numbers and eventually part of them spread to Asia and Europe. It took them a long time to recover and finally outnumber the Khoisan.
Khoisan is the language with all the clicks in it (yeah, been watching Trevor Noah today).
In comparison, between the spread of that sound structure (culture, so to speak) vs genetic distribution, why would one spread wide and the other part not?
Or am I wrong about clicks being a rarity in languages of the continent?
We can trace human lineages by following either the Y-chrosome DNA or the mitochondrial mtDNA. For all of the other chromosomes the DNA of the mother and the DNA of the father are shuffled together, but Y DNA comes only from the father and mtDNA comes over from the mother, and these genes only change as a result of random mutations.
If you find a group of men who all share a specific mutation on the Y chromosome, then they all share some common ancestor where that mutation first occurred.
That rate of mutation is constant per birth, so you'll find the greatest genetic diversity in places where it has been accumulating for a long time.
Also, if that population shrinks precipitously, then that population bottlenecks can be measured in the genetic diversity of the descendents thousands of years later. (And genetic drift can become locked in).
The researchers determined that humanity suffered a population bottleneck some ~100,000 years ago, which may have been related to a changing, drier climate. By looking at the genetic diversity preserved, they also determined that the population bottleneck suffered by the ancestors suffered by non-Africans must have been significantly more severe than the bottleneck seen in the ancestors of the Ju/'hoansi. 100,000 years ago must have been a pretty good time to live in southern Africa (compared to the rest of the continent).
Anyway, I believe that click languages were once widespread. The greatest genetic distance between any two populations on Earth is between the Ju/'Hoansi (in Southern Africa) and the Hadzabe (in East Africa). They both speak click languages, and those languages are unrelated.
I believe that at some time (between 150,000 and 70,000 years ago), all of humanity lived in a range from South Africa to East Africa and all spoke click languages. At some point, possibly as a result of the climatic event discussed in this paper, the genetic histories of the Hadzabe, the Ju/'hoansi, and another group diverged. That last group stopped speaking in clicks and also conquered the world: all the rest of humanity is ultimately descended from this small group. About 1500 years ago, Bantu farmers swept through southeast Africa and left the speakers of click languages persisting only in isolated deserts that couldn't be farmed.
To your exact question, I'm not sure. The Bantu expanded from a small region of west Africa beginning around 3000 years ago; it's plausible that it took them a while to overwhelm southeast Africa.
What I find really interesting is that we have actual historical records from the great civilization of the time, Egypt, that predate the Bantu. We even have records of their diplomacy with the non-Bantu kingdoms to their south. The Africans they write about (and, in some cases, draw artwork of) bear little relation to the Africans we know today. Sure, expanding human populations have wiped out incumbents everywhere in the world, but it's unusual for the eye of recorded history to be so nearby when it happens (North America would be the best example, I guess, but I'm pretty sure the Bantu expansion is #2).
The non-Khoisan languages Xhosa and Zulu (30 million+ speakers in South Africa, now far greater than the Khoisan languages) also have clicks, but in smaller numbers.
One of the UCT Linguistics professors had a theory that the clicks that infiltrated Xhosa and Zulu (and not other languages) were due to a tradition in which engaged women had to avoid saying the letters in the names of their fiance's male relatives. Clicks from neighbouring Khoisan populations entered the languages as a strategy to help much more recently than the split this article is talking about.
Compare the headline with a nonrandomly-chosen sentence from the paper:
Headline: Khoisan hunter-gatherers have been the largest population throughout most of modern-human demographic history.
Paper: Our hypothesis may [...] suggest that the Khoisan hunter-gatherers and their ancestors have been the largest population in terms of genetic diversity throughout modern-human history. (emphasis added)