Din Online, one of the many "ask a rabbi" services online, wrote in an answer that usage of this phrase is custom but there's no law that formalizes it. They add that it is usually used for someone you had some connection to -- close personal relationships for sure, but it can also be used for other people you knew or even people who inspired you but who didn't know you.
This matches my experience -- people will of course say zichrono/zichronah livracha for family members and close friends, but people also say it of teachers they once had, coworkers, leaders... I heard people who never met her refer to Ruth Bader Ginsburg this way, for example. But I don't think I've ever heard somebody refer to Rashi that way, even though he was a great rabbi centuries ago.
In my liberal circle I've heard people use the phrase for both Jews and non-Jews. I don't know how common it is in more traditional circles to refer to non-Jews this way. It's not that non-Jews aren't important (they are), but I don't know how specifically Jewish this designation is meant to be.
The phrase literally means "his/her memory for blessing"; the "may" is implied, but it can also be understood as "his/her memory is for a blessing", and I've heard people use it that way (and have used it that way myself). I understand that it's kind of a double meaning: I know this person was someone who deserves to be remembered for good, and I want other people to understand that too -- so it's both an assertion (for the speaker) and a wish (for the listener). This might be related to Proverbs 10:7, which says that the memory of the righteous is for blessing.