I'm not completely clear on what answer would be considered satisfactory, but here's one categorical way to think about tracing in $\mathbf{Bij}$.
The morphisms of the symmetric monoidal category with duals obtained by applying the Joyal-Street-Verity construction to $\mathbf{Bij}$ can be pictured in terms of string diagrams that are essentially 1-cobordisms, i.e, curves bounded by compact 0-manifolds that are built from string diagrams for permutations and from cups and caps (which are counits and units of dual pairs) by applying the usual composition and juxtaposition operations. Now cobordisms generally are certain types of cospans in the category of manifolds. Thus, what we can do is consider $\mathbf{Bij}$ (or more generally $\mathbf{Set}$) as embedded in the bicategory of cospans between sets, where a bijection or function $\sigma: A \to B$ is mapped to the cospan
$$A \stackrel{\sigma}{\to} B \stackrel{1_B}{\leftarrow} B.$$
Composition of cospans (i.e., of 1-cells)
$$(A \stackrel{f}{\to} B \stackrel{g}{\leftarrow} C) \; ; \; (C \stackrel{h}{\to} D \stackrel{k}{\leftarrow} E)$$
is obtained by taking the pushout of $g$ and $h$, and composing $f$ and $k$ with the pushout coprojections. The disjoint sum induces an obvious tensor product on cospans.
The category obtained by taking isomorphism classes of 1-cells is a symmetric monoidal category $\mathbf{Cospan}$ with duals, in which each object is dual to itself. This works in a manner dual to the situation for $\mathbf{Span}$, where the unit and counit are given by "equality predicates"; thus for each object $U$, the unit and counit of $U \dashv U$ are given by coequality cospans
$$\eta_U = (0 \to U \stackrel{\nabla_U}{\leftarrow} U + U), \qquad \epsilon_U = (U + U \stackrel{\nabla_U}{\to} U \leftarrow 0).$$
Thus, given a bijection $\sigma: A + U \to B + U$, the tracing $Tr_{A, B}^U(\sigma)$, given by a composite of cospans
$$A \cong A + 0 \stackrel{1_A + \eta_U}{\to} A + U + U \stackrel{\sigma + U}{\to} B + U + U \stackrel{1_B + \epsilon_U}{\to} B +0 \cong B,$$
can be read off by taking a pushout in $\mathbf{Set}$ of the diagram
$$A + U \stackrel{1_A + \nabla}{\leftarrow} (A + U + U \stackrel{\sigma + U}{\to} B + U + U \stackrel{1_B + \nabla_U}{\to} B + U)$$
and then composing the pushout coprojections with the canonical inclusions $A \hookrightarrow A + U$, $B \hookrightarrow B + U$.
That's a precise categorical description of the trace operation in terms of pushouts in $\mathbf{Set}$. A priori, the result is a cospan from $A$ to $B$, but a little reflection shows that it's actually a bijection from $A$ to $B$ (i.e., a cospan obtained by applying the inclusion functor $\mathbf{Bij} \hookrightarrow \mathbf{Cospan}$ to a suitable bijection).
It's not hard to see what is really going on. Tracing is basically the introduction of a feedback loop where outputs of $\sigma$ in $U$ are fed back in as inputs in $U$ living in $A + U$, and iterating through cycles until you exit $U$. That's exactly what the string diagram picture suggests (here rephrased in terms of a cospan composition), and the meaning in terms of the cycle decomposition is clear. For instance, to take the example of the OP, we have in one of the cycles of $\sigma$ a path $5 \to 8$; this output $8 \in U$ is reinterpreted as an input where the next step in the cycle is $8 \to 3$, at which point we have exited out of $U$.