I just found a seminal article on complexity written by Renate Bartsch in 1973 (in German). It is a very good summary of the perspective on this topic at the beginning of the ‘70s. The generative grammar background research on language starts to be criticized, but it is still a landmark and a framework (most notably the reflexion on surface and deep structure).
R. Bartsch, “Gibt es einen sinnvollen Begriff von linguistischer Komplexität ?” Zeitschrift für Germanistische Linguistik, vol. 1, iss. 1, pp. 6-31, 1973.
Bartsch focuses on three main aspects of the problem to answer this question: does the idea of linguistic complexity make sense ?
The framework of the transformational grammar alone cannot be trusted
when it comes to measuring complexity, because the surface complexity
does not account for a potential underlying complexity.
Bartsch quotes the interviews made by Labov and his conclusions stating that the dialect difference is to be found on the surface without having anything to do with the logic of a sentence.
This is by far the most interesting part of the article, lots of
criteria for linguistic complexity are analyzed with examples (some in German).
Bartsch also writes about complexity metrics and claims that there is no homogeneous way to measure complexity, one has to consider several perspectives, each one being a part of psychological complexity. What counts is the understanding difficulty which cannot be addressed using reaction times.
According to Bartsch it is necessary to have a linguistic theory, a cognitive one and one about perception available to analyze this phenomenon.
Language evolution theory
Bartsch states that language evolution only means grammatical
simplification in a few cases. A simplification on one hand may lead to
more difficulties on the other. Shorter sentences for instance can be
perceptively more difficult to understand.
Then she deals with the Subject - Verb - Object order and compares the evolution of English and German regarding linearity.
Finally, phonological changes are mentioned.
Renate Bartsch concludes that linguistic complexity is a balanced phenomenon which requires to take all its sides into account. In a way, it is the kind of approach which led to the idea of language as a complex system.