Can the composite of two smooth relations fail to be smooth?

Your conjectured counterexample works perfectly.

Let $P = \{(a,b): a^2+b^2=1\}$ and $Q=\{(b,c):b^2+c^2=1\}$.

Then $$\begin{align} (a,c)\in Q\circ P &\iff \exists b:a^2+b^2=1 \text{ and } b^2+c^2=1 \\ &\iff \pm\sqrt{1-a^2} = \pm\sqrt{1-c^2} \\ &\iff a^2=c^2 \text{ and } a^2,c^2\le 1. \end{align}$$

Thus $Q\circ P$ looks like an X, which is not a manifold. Consider the top view of this figure:

^{Paul Bourke, "Intersecting cylinders", 2003}

First, let me make sure I understand. Let $A$ and $B$ be manifolds. By a relation $A \to B$, you mean a subset of $A \times B$, and such a relation you call smooth if that subset is a smooth submanifold. If it is okay, I would prefer to stick with the subset terminology—calling a subset of a manifold smooth if it is a smooth submanifold.

1. Given a subset of manifold $A$ and a subset of manifold $B$, their product is a subset of $A \times B$, and if those subsets are smooth, so is their product.
2. $A$ itself is a smooth subset of $A$.
3. Given a subset of $A \times B$, its projection to $A$ is the collection of $a$ in $A$ such that, for some $b$ in $B$, $(a, b)$ is in the given subset. It is false in general that the projection of a smooth subset is a smooth subset.
4. Given two subsets of $A$, their intersection is a subset of $A$, but it is false in general that the intersection of two smooth subsets is smooth.

In terms of these, we can describe your construction as follows. Let there be given a subset $P$ of $A \times B$, and a subset $Q$ of $B \times C$. First, take $P \times C$—a subset of $A \times B \times C$—and $A \times Q$—also a subset of $A \times B \times C$. Second, intersect those two subsets. And third, project that intersection to $A \times C$. That is, we get from relations $A \to B$ and $B \to C$ to a relation $A \to C$. Now, in the case in which $P$ and $Q$ are smooth, the first step above will result in smooth subsets, but the second and third, in general, will not. So, your construction would not be expected to yield a smooth subset.