This seems to address your concern completely?
So this could substantially underrepresent vocabularies. There are only so many unique words you can put in a sentence. As an extreme, if we looked at the first hundred words of every rapper, we would not find a hundred unique words in any of them: (due to repeats of grammatically common words) even though, clearly, all rappers have a vocabulary over a hundred.
I wonder if this is a fatal flaw? How can we estimate where the distortion stops? (For example, if someone uses 1000 words in their first 35,000, intuitively this seems to imply to me that's most of their stock. But if someone uses 5,000 in 35,000 - that is not so clear at all.)
A second related problem that that paper touches on toward the end is that sequential words from the same text are not independent samples from an author's vocabulary. Two artists may have the same vocabulary, but if one artist uses more non-sequiturs, fewer articles, fewer repeated phrases, or generally tries to use more unique words within a given song, then that artist will come out ahead in the measure used here. I'm not sure how much of a problem this really is for comparing lyrics between artists (depending on what is of interest, it may actually be desirable), but it may explain the poor showings for Shakespeare and Melville, since prose is likely to repeat words more frequently than rap lyrics for reasons unrelated to the authors' vocabularies. (FWIW, even conservative estimates put Shakespeare's vocabulary at >15,000 words, which would be hard to measure in a sample of 35,000 words.)
mdaniels.com/vocab/scatter.png
so the average would change as your sample size grows.
35K was the threshold where things didn't get garbled (like the 100 word example that you mention).
The threshold is also impacted by who I include. If I went to 50K, I'd lose out on rappers like Drake.
Edit: A quick check found 7 repetitions of the same 8 word phrase in a DMX song. Which I chose becase he was at the bottom of the list. http://www.azlyrics.com/lyrics/dmx/whatthesebitcheswant.html
The underlying problem is one of estimating the cardinality of a multinomial distribution given a fixed number of samples. In isolation this problem is ill-posed, since it is always possible that there is a word in a given lyricist's vocabulary that he uses with very low frequency and that is unlikely to appear in any sample, but with appropriate prior information it may be possible to obtain an accurate estimate.
This is not my field, but a brief Google Scholar search shows that there are several papers on estimating vocabulary size, or equivalently, estimating the number of species based on sampling. There is a somewhat dated review (http://cvcl.mit.edu/SUNSeminar/BungeFitzpatrick_1993.pdf) that details some methods of estimation (in this case, I believe we are in the domain of "infinite population, multinomial sample" with unequal class sizes). The paper notes that there is no unbiased estimator available without assumptions on the distribution of word use frequencies, but some of the proposed estimators may be more accurate than the naive estimate used here.