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}