Looks like the 1920s - https://books.google.com/ngrams/graph?content=constructive+c... .
For example, here's a 1919 source which uses that phrase three times: https://books.google.com/books?id=FFccAQAAMAAJ&q=%22construc... .
As for the essay, "constructive criticism" means two things. One is feedback, which can be negative, designed to improve things. Peer review of scientific papers is sometimes a form of constructive criticism.
Another - the one the essay highlights - is when 'constructive criticism' is used as cover for punching down, in order to minimize the negative repercussions.
(It's also a way to enforce a "tall poppy syndrome" culture, but the essay didn't mention that type of 'constructive criticism.'
"Devil's advocate" is a similar term with two different meanings. In the best of cases, it's someone who gives negative criticism meant to highlight the flaws in a proposal, even if the speaker is not against the proposal. In practice it's more often used as a cover for someone who wants to make a negative comment without putting much thought into the topic, and who doesn't want the triteness of the comment to be interpreted as personal ignorance.