Assuming you know basic coding and are able to write a simple script doing the input and writing the output for all the 4 million calculations you can use for example this script I found some days ago for doing the alignment and RMSD calculation. Alternatively PyMol can do this too (align function).
Not quite sure about the timing*, even if one would take a second, I expect it to be much faster, that's still about two days if run in sequence. If you are doing this only once it might not be worth the effort to optimize this and I'd rather wait some hours or days or run several of those jobs in parallel on a cluster.
*I've made a similar script and reading the xyz files, calculating the RMSD and even saving the aligned structures takes about 5 ms, which means it's done in less than 6 hours even without running it in parallel.