$\newcommand{\sh}{\stackrel{\mathrm{h}}{\mbox{—}}}\newcommand{\sv}{\stackrel{\mathrm{v}}{\mbox{—}}}\newcommand{\sp}{\stackrel{\mathrm{p}}{\mbox{—}}}$Here's a proof for groups (no finiteness assumed).
Statement. Let $X_G$ be $G\times G$ endowed with this binary relation. Then if there is an isomorphism $X_G\to X_H$ then $G$ and $H$ are isomorphic groups.
Observe that this binary relation on $G$ is the union of 3 equivalence relations: horizontal, vertical, product $$(a,b)\sh (a',b),\quad (a,b)\sv (a,b'),\quad (a,b)\sp (as,s^{-1}b),\quad a,b,s\in G.$$
Observe that the intersection of any two of these three equivalence relations are reduced to the equality relation.
Let us study complete subgraphs in this binary relation. Call "pure" ones the obvious ones, i.e., subsets that are in a single equivalence relation for one of these three equivalence relations. Let us now study the non-pure ones.
Clearly, a subset of cardinal three of $G\times G$ that is a complete subgraph is either pure or consists of three distinct pairs $x,y,z$ with $x\sh y \sv z\sp x$.
Now consider a subset of cardinal four that is a complete subgraph, say $x,y,z,w$ with $x,y,z$ as above. If by contradiction $x\sh w$, then $y\sh w$. The triangle $zxw$ has edge labels p, h, hence the third label is v, namely $z\sv w$, and hence $y\sv w$ by transitivity. So both $y\sh w\sv y$, so $w=y$, contradiction. We get a similar contradiction if $x\sp w$. So eventually $x\sv w$, $y\sp w$, $z\sh w$. In particular, we see that the labels in the three edge from $x$ are distinct.
We deduce that every complete subgraph of cardinal $\ge 5$ is pure. This allows to characterize, if $|G|\ge 5$, the pure equivalences classes as the maximal complete subgraphs of cardinal $\ge 5$. It follows that for every graph isomorphism $X_G\to X_H$, for $G$, $H$ of cardinal $\ge 5$, the isomorphism permutes the three equivalence relations in some way.
Now let us observe some symmetries. First, $G\times G$ acts transitively on this graph as $(g,h)(a,b)=(ga,bh^{-1})$ (call this "translation"). Second, there are automorphisms permuting the 3 relations: precisely, $(a,b)\mapsto (b^{-1},a^{-1})$ fixes $\sp$ and switches $\sh$ and $\sv$. Second, $(a,b)\mapsto (ab,b^{-1})$ preserves $\sh$ and switches $\sv$ and $\sp$.
Hence, for $G,H$ of cardinal $\ge 5$, if there is an isomorphism $X_G\to X_H$, then we can compose it by some automorphism of $X_H$ to ensure that it preserves each of the relations $\sh$, $\sv$, $\sp$. Moreover, composing by a translation ensures that it maps $(1_G,1_G)$ to $(1_H,1_H)$.
Now let $f$ be such an isomorphism $X_G\to X_H$. It preserves the $\sh$-class of $1$, hence maps $(g,1)$ to $(\sigma(g),1)$ for some bijection $\sigma:G\to H$. Similarly it maps $(1,g)$ to $(1,\psi(g))$ for some other bijection $\psi$.
For each $g$ have $(1,g)\sp (g,1)$, so $(1,\psi(g))=f(1,g)\sp f(g,1)=(\sigma(g),1)$, hence $\psi(g)=\sigma(g)$. Thus $\psi=\sigma$.
For $g,h\in G$, the element $(g,h)$ is uniquely characterized by the property $(g,1)\sv (g,h)\sh (1,h)$. So $(\sigma(g),1)=f(g,1)\sv f(g,h)\sh f(1,h)=(1,\sigma(h))$. Using uniqueness, we deduce $f(g,h)=(\sigma(g),\sigma(h))$.
Now $(g,h)\sp (gh,1)$, so $$(\sigma(g),\sigma(h))=f(g,h)\sp f(gh,1)=(\sigma(gh),1),$$ which means $\sigma(gh)=\sigma(g)\sigma(h)$. Since this holds for all $g,h$, this proves that $\sigma$ is a group homomorphism $G\to H$. Since it is bijective, it is an isomorphism.
It remains to deal with the case of order $4$ (of course if one of the two groups has order $4$, so does the other). In general, it is enough to count the number of non-pure complete subgraphs of cardinal 4 in a group $G$, containing $(1,1)$. By a straightforward argument, its elements have to have the form $(1,1)$, $(1,x)$, $(x,1)$, $(x,x)$ with $x$ of order $2$. Thus there are as many as elements of order $2$. This distinguishes between cyclic-4 and Klein.