The operation you are describing is a cartesian closed structure, not on the category $Rel$ of sets (as objects) and relations (as morphisms), but rather on a category whose *objects* are relations and whose morphisms are pairs of functions mapping related arguments to related results. This is a bit easier to see/explain if instead of considering (binary) relations, we consider (unary) predicates.

So, let $SubSet$ be the category whose objects are pairs $(A,P\subseteq A)$ of a set together with a predicate on that set, and whose morphisms $(A,P) \to (B,Q)$ are functions $f : A \to B$ mapping arguments in $P$ to results in $Q$:
$$\forall a.\, a \in P \Rightarrow f(a) \in Q$$
There is an obvious functor $\pi : SubSet \to Set$ given by the first projection. Now, the key fact is that **$\pi$ is a strict cartesian closed functor**. This means that for any pair of predicates $P \subseteq A$ and $Q \subseteq B$, there are predicates
\begin{align*}
P\times Q &\subseteq A \times B \\
Q^P & \subseteq B^A
\end{align*}
such that $(A\times B,P\times Q)$ and $(B^A,Q^P)$ are respectively the product and exponential in $SubSet$. In particular, $P\times Q$ and $Q^P$ are defined by
\begin{align*}
(a,b) \in (P\times Q) \quad &\text{iff}\quad a\in P \wedge b\in Q \\
f \in Q^P \quad &\text{iff}\quad \forall a.\,a\in P \Rightarrow f(a)\in Q
\end{align*}
Essentially the same explanation goes through in the case of binary relations, but in that case we consider a category $Sub(Set\times Set)$ equipped with a projection functor $\pi' : Sub(Set\times Set) \to Set\times Set$. Once again the key point is that $\pi'$ is a strict cartesian closed functor. Note that these projection functors have some other important properties as well (for example, they are bifibrations), but for the construction alluded to in your question this cartesian closed structure suffices.

Finally, if you are interested in reading more about this categorical approach to "logical predicates", you might have a look at Hermida's thesis (as well as some of the followup literature):