The definition of "homomorphic relation" for groups in the question only refers to the multiplication, but it is more natural also to require compatibility with inverses (because we are not talking about semigroups which happen to be groups, but about groups; although it is well-known that the forgetful functor is fully faithful, i.e. the homomorphisms are the same, this is not the case for the "homomorphic relations"). Then homomorphic relations $R$ on a group correspond 1:1 to normal subgroups $N$ of the group (via $(x,y) \in R \Leftrightarrow x y^{-1} \in N$). More generally, a congruence relation on an algebraic structure is an equivalence relation on the underlying set which is compatible with all the operations. Equivalently, the quotient of the underlying sets becomes an algebraic structure of the same signature such that the projection becomes a homomorphism. The homomorphism theorem holds in this general setting. I hope that this refutes the claim that we never see homomorphic relations.
The Yoneda Lemma holds for enriched categories over symmetric monoidal closed categories, and $\mathsf{Rel}$ is a symmetric monoidal closed category, with tensor product $(X,R) \otimes (Y,S) = (X \times Y,R \times S)$, where $R \times S$ abbreviates the relation $\{((x,y),(x',y')) : (x,x') \in R, (y,y') \in S\}$.
Note that $\mathsf{Set}$ has many more convenient properties than $\mathsf{Rel}$. For example, Milius' paper On Colimits in Categories of Relations explains that $\mathsf{Rel}$ has not all colimits of $\omega$-chains.