Any insight as to why FASM would say these two instructions ('movlhpd', 'movhlpd') are illegal? Just not been implemented maybe?

Edit: It doesn't seem gas recognizes them either.

That is for a good reason, the processor has no such instuctions.

Why would it appear on this page and why would r22 have used it in his code in this thread in that case?

I can't personally comment on other people postings but check the processor manuals from Intel and AMD, you won't find them listed. There are other instructions that can do the same thing so there is no need for such instructions.

Which instruction(s) should I replace these with?

Thanks, btw

MOVHLPS & MOVLHPS will work correctly with both single and double floats, also check out PSHUFD which generalises the data movements.