An index is a list of words, and the place they occur. E.g. games occurs on row 123 and 456. If you have such a list with all words, you can easily search for the word that matches best. This way, you could match gmes with games.
However, this is not possible with the index MySQL provides.
You could use an API like Yahoo's Spelling Suggestion as any easy way of completing it with out having to roll your own.
if you're not planning to rely on 3rd party sites, you definitely need your own dictionary with levenshtein algorithm to find out how close the user entries are to the dictionary terms
Another option would be the PHP Pspell functions in particular pspell_suggest, but you need to install the aspell library on the server.
You could use Yahoo Spelling API etc. if your queries are very generic. But if you have a domain specific vocabulary then you are better off using Apache Solr.
You can use it to index your 2MM records, easy! And use it as a search server with faceting etc. It also generate a spell-checker index out of your records which you can use for your "did you mean"? or the auto-suggest feature. It is also exceedingly simple to integrate into any language because of its RESTful API
Bottom-line: if you are looking for a long-term solution that can handle several things, in addition to spell-checking, such as search/auto-suggest/faceting etc. Solr is the way to go.