Query Efficiency - Filter people when name and surname are different columns, and string may appear in any of them
If it is an innodb table you could just use 'match':
(see https://dev.mysql.com/doc/refman/8.0/en/fulltext-natural-language.html)

SELECT * FROM users WHERE MATCH (name, surname1, surname2) AGAINST ('Mark Paul' IN NATURAL LANGUAGE MODE);


But honestly i have no idea how it performs with millions of entries...

Cheers
Olaf