Coordinate-free proof of $\operatorname{Tr}(AB)=\operatorname{Tr}(BA)$?

$\newcommand{\tr}{\operatorname{tr}}$Here is an exterior algebra approach. Let $V$ be an $n$-dimensional vector space and let $\tau$ be a linear operator on $V$. The alternating multilinear map $$ (v_1,\dots,v_n) \mapsto \sum_{k=1}^n v_1 \wedge\cdots\wedge \tau v_k \wedge\cdots\wedge v_n $$ induces a unique linear operator $\psi: \bigwedge^n V \to \bigwedge^n V$. The trace $\tr(\tau)$ is defined as the unique number satisfying $\psi = \tr(\tau)\iota$, where $\iota$ is the identity. (This is possible because $\bigwedge^n V$ is one-dimensional.)

Let $\sigma$ be another linear operator. We compute \begin{align} (\tr\sigma)(\tr\tau) v_1 \wedge\cdots\wedge v_n &= \sum_{k=1}^n (\tr\sigma) v_1 \wedge\cdots\wedge \tau v_k \wedge\cdots\wedge v_n \\ &= \sum_{k=1}^n v_1 \wedge\cdots\wedge \sigma \tau v_k \wedge\cdots\wedge v_n \\ & \qquad + \sum_{k=1}^n \sum_{j \ne k} v_1 \wedge\cdots\wedge \sigma v_j \wedge \cdots \wedge \tau v_k \wedge\cdots\wedge v_n. \end{align}

Notice that the last sum is symmetric in $\sigma$ and $\tau$, and so is $(\tr\sigma)(\tr\tau) v_1 \wedge\cdots\wedge v_n$. Therefore $$ \sum_{k=1}^n v_1 \wedge\cdots\wedge \sigma \tau v_k \wedge\cdots\wedge v_n = \sum_{k=1}^n v_1 \wedge\cdots\wedge \tau \sigma v_k \wedge\cdots\wedge v_n, $$ i.e. $\tr(\sigma\tau)=\tr(\tau\sigma)$.

---

EDIT: To see that the trace is the sum of all eigenvalues, plug in your eigenvectors in the multilinear map defined at the beginning.

The proof in Martin Brandenburg's answer may look scary but it is secretly about moving beads around on a string. You can see all of the relevant pictures in this blog post and in this blog post. The proof using pictures is the following:

In the first step $g$ gets slid down on the right and in the second step $g$ gets slid up on the left.

You can also find several proofs of the stronger result that $AB$ and $BA$ have the same characteristic polynomial in this blog post.

The trace of an endomorphism $f : X \to X$ of a dualizable object $X$ in a monoidal category is the composition $1 \xrightarrow{\eta} X \otimes X^* \xrightarrow{f \otimes \mathrm{id}} X \otimes X^* \cong X^* \otimes X \xrightarrow{\epsilon} 1$. This coincides with the usual definition in the category of vector spaces. There is a more general categorical notion of trace, which then also applies to Hilbert spaces. Under suitable assumptions the formula $\mathrm{tr}(f \circ g)=\mathrm{tr}(g \circ f)$ holds. For more details, see the paper Traces in monoidal categories by Stolz and Teichner.