Approximate Similarity Search
Your method is reasonable.  There are other possibilities as well.

Randomized algorithm: locality-sensitive hashing

Here is a randomized algorithm that finds all matches with high probability (probability $1-\epsilon$ where $\epsilon$ is exponentially small, but not zero).  It will probably be more efficient.

Build 100 tables.  Each table is constructed as follows: Randomly pick a subset of 8 positions (out of the 64 possible positions).  Now a string is hashed by keeping only the 8 characters from those 8 positions, and the string is stored in the hashtable keyed on that hash.  For instance, if the positions associated with a particular table are $i_1,i_2,\dots,i_8$, then the string $S$ is hashed by hashing $S[i_1],S[i_2],\dots,S[i_8]$ and using that hash value as the key to store $S$ in the table.  Each table has a different and randomly generated subset of positions.

Store each of the millions strings in all 100 tables.  When you get a query string $Q$, look it up in each of the 100 tables to find all possible matches, take the union of those possible matches, and calculate the Hamming distance between $Q$ and each possible match.

This is very similar to your method, but each "part" is longer (8 characters instead of 4 characters), so there will probably be many fewer "false matches" from the hashtable.

There is no guarantee that this approach will find all valid matches, but most likely it will.  The probability that a valid match is not found is

$$(1-(49/64)^8)^{100} \approx 0.0000035,$$

so missing a match is unlikely.  You can tune the probability of a missed match by adjusting the number of tables, and you can adjust the parameters ($8,100$) to find the setting that gives you the best possible performance.

This is effectively a form of locality-sensitive hashing (LSH).  There may be other schemes worth investigating.  You could also look at MinHash.

Trie

Another approach is to store the dictionary of millions of strings in a trie data structure.  Given a query string $Q$, you can start traversing the trie, doing a recursive breadth-first search  to explore all paths that are at distance at most 15 from $Q$.  For many paths, you'll be able to immediately terminate the search.