I was very curious about this claim and it seems that's not quite right. Of course the phrase "essential complexity" was applied to non-software topics before Brooks (Wikipedia correctly notes that the distinction between essence and accident goes back to Aristotle), but it seems Brooks was not the first to apply it to software either. I would not deny that he popularized it.
Note that there's another result that claims to be from 1968 but the text of the book says it's from 1996.
Interestingly "essential complexity" was used earlier and more often than "accidental complexity", probably because the former sufficiently implies the existence of the latter.