How could language have evolved?

An eminent group of co-authors (Bolhuis, Tattersall, Chomsky, and Berwick) suggest that a simple core repeatable operation is the basis of all language. This open source article is a "must read" item for anyone interested in the structure and evolution of language, and I pass on just the abstract and a bit on the basic model:

The evolution of the faculty of language largely remains an enigma. In this essay, we ask why. Language's evolutionary analysis is complicated because it has no equivalent in any nonhuman species. There is also no consensus regarding the essential nature of the language “phenotype.” According to the “Strong Minimalist Thesis,” the key distinguishing feature of language (and what evolutionary theory must explain) is hierarchical syntactic structure. The faculty of language is likely to have emerged quite recently in evolutionary terms, some 70,000–100,000 years ago, and does not seem to have undergone modification since then, though individual languages do of course change over time, operating within this basic framework. The recent emergence of language and its stability are both consistent with the Strong Minimalist Thesis, which has at its core a single repeatable operation that takes exactly two syntactic elements a and b and assembles them to form the set {a, b}.

...it appears that human language syntax can be defined in an extremely simple way that makes conventional evolutionary explanations much simpler. In this view, human language syntax can be characterized via a single operation that takes exactly two (syntactic) elements a and b and puts them together to form the set {a, b}. We call this basic operation “merge”. The “Strong Minimalist Thesis” (SMT) holds that merge along with a general cognitive requirement for computationally minimal or efficient search suffices to account for much of human language syntax. The SMT also requires two mappings: one to an internal conceptual interface for thought and a second to a sensory-motor interface that externalizes language as speech, sign, or other modality. The basic operation itself is simple. Given merge, two items such as the and apples are assembled as the set {the, apples}. Crucially, merge can apply to the results of its own output so that a further application of merge to ate and {the, apples} yields the set {ate, {the, apples}}, in this way deriving the full range of characteristic hierarchical structure that distinguishes human language from all other known nonhuman cognitive systems.