There's no builtin support in "#ifexpr:" or "#if:" to compare strings. You need another parserfunction, for example you can use "#invoke:" via Scribunto, to call a function defined by a Lua module. Note however that Lua basically performs a lexicographic comparison of strings with its "<" operator, it does not trim them, does not parse any HTML (not even HTML comments that may be present in parameters), does not convert HTML character entities, does not normalize strings, and then does not perform any UCA collation (so "é" would sort *after* "f" and not between "e" and "f").
You may want to call:
{{#ifeq: {{{1|}}} | {{{2|}}}
| <!-- empty -->
| {{#ifexpr: {{#invoke:Modulename|compare|{{{1|}}}|{{{2|}}}}} < 0
| {{#ifexist: Category:Relations of {{{1|}}} and {{{2|}}}
| [[Category:Relations of {{{1|}}} and {{{2|}}}]]
| [[Category:Relations of {{{2|}}} and {{{1|}}}]]
}}
| {{#ifexist: Category:Relations of {{{2|}}} and {{{1|}}}
| [[Category:Relations of {{{2|}}} and {{{1|}}}]]
| [[Category:Relations of {{{1|}}} and {{{2|}}}]]
}}
}}
}}
However this does not resolve the redirects (#ifexist are giving false hints). For that you need a Lua module that can not only test the effective existence iof either links, and then detect if one is a redirect and get its target (it has to load the page and parse its begining, because MediaWiki still does not expose in Lua if a page is a redirect and what is its target; MediaWiki internally parse pages and detects that and maintain that in a cache that is used when loading any page name via some links, but it does not index that information in an accessible way; loading and parsing the page manually in Lua is a bit costly and errorprone due to the MediaWiki syntax).
So the best way you can do is to use your template with parameters 1 and 2, not perform any test on them. But then update the page containing tranclusions of your template using the explicit parameters values in the correct order (and then swap that order if one is a redirect).
There are other caveats: the parameters 1 and 2 may contain disambiguation suffixes, that may be removed in the binary relation (e.g. "Paris, Texas" and "Austin, Texas": would you name your category as "Relations of Austin, Texas and Paris, Texas", or as "Relations of Austin and Paris (Texas)"... Beware that naming pages automatically is tricky, there are frequently "aliases" (e.g. "Relations of France with the United States" or the reverse, note that there may be other way to express the combination), and some preferences that may change over time (or will need to take into account some decisions, not always the same between countries or languages, and sometimes conflicting). As well you have to manage the possible insertion of articles (like "the" in English) before some entity names, which may not be present when entity names are used alone in page names (e.g. with "United States": "Relations of France and the United States", "Relations of the United Kingdom and the United States", "Relations of the United States and Vietnam").
Such binary relations with arbitrary combination should be avoided, they explode exponentially and are a nightmare to maintain (e.g. for 200 countries, you get almost 40,000 relations, and most of them will be empty; and for ternary relations you'd reach about 8,000,000!). They should be created manually and added individually where relevant.