I thought it was a misconception that Shakespeare added so much new words - him being a prolific and very popular writer, and with much of his corpus surviving to this day, his works get cited whenever there's a "first use" mentioned somewhere.

The fact that one of his plays is the oldest written source where a word was seen for the first time in written form doesn't mean that it wasn't in common use before that; indeed it could mean the opposite – because the spectators of his plays should be able to understand what the characters are speaking, not leave befuddled in need of translation.

Sure, it's contentious, what's not contentious is that our lexicon grows over time, how would an AI go about inventing a new word?

The same ways we do: by scissors-and paste with parts of other words. Most if our English words are small alterations of proto-indo-european words.