People working on language evolution in the intellectual tradition you describe believe the following things (I limit myself to give an accurate rendering of their positions; as none of the opinons described below are part of the scientific consensus).
1) Language is a core human faculty, fundamentally different from animal communication; which they take to be an analogous organ but not a homologous one. The genetic encoding of this faculty is very simple.
2) This core human faculty evolved rapidly, probably only once in the Homo Sapiens evolutionary history at least 20,000 years ago but probably at most 100,000 years (this they believe because on the one hand the ability to learn any human language shows no genetic diversity between populations which separated 20,000 years ago at least and on the other hand there are few indisputable archeological artifacts with a symbolic meaning dating from before 100,000 years ago).
3) Crucially for your question, syntactic structures are fundamentally very simple, in fact as simple as they could be, and exhibit (at a fundamental level) only very small and trivial cross-linguistic variations.
For them, these three simultaneous opinons are mutually reinforcing and present a coherent picture. For instance, if it is true that 2) the human faculty for language evolved once and relatively recently, then its genetic encoding is in all likelihood very simple, so 1), and so should be its expression 3). Conversely, if you believe 3), then the question of why all human languages should be fundamentally the same naturally arises, and the null-hypothesis would be a combination of 1) and 2). I should say that they also firmly believe that
4) Evolution of the human capability of language is for the moment way to hard a problem, as is already in fact evolution of immensely simpler cognitive faculties.
To answer your precise questions.
[Do they] conclude that the language of our ancestors 1 million years ago already had the capability to construct recursion? Absolutely not. They very strongly believe that our closest ancestors at that time scale lacked the current human capability of language. The time scale they propose is an order of magnitude lower.
Is the information about language encoded in some other way (which way?)? Much simpler biological phenomena show a delicate interplay between genetic, epigenetic and environmental factors, so the null-hypothesis is that the same should be the case for the language faculty. In view of 4), they would probably say that this question is (way) too hard for current science.
What else solves my apparend misunderstanding? Actually, your reasoning was quite parallel to theirs, but you took as a premise the fact that linguistics structure are complex (to quote from your question with my emphasis "so within a few 100.000 of years, the information about complex linguistic[s] structures is very unlikely to be encoded into the DNA"). They would agree with your assessment if they considered linguistics structures to be complex, but they believe they are simple.
Sources
1,2