According to this paper, given the finite field extension $L:K$ and $\alpha\in L$, we define the trace $\text{Tr}_{L:K}(\alpha)$ as the trace of the linear transformation $$m_\alpha:L\rightarrow L:x\mapsto \alpha x$$
The paper then argues that "if we build a $K$-basis of $L$ by first picking a basis of $K(\alpha )$ and then picking a basis of $L$ over $K(\alpha )$, we get a ‘block’ matrix for $m_{\alpha}$ consisting of $[L : K(\alpha )]$ copies of the smaller square matrix for $m_{\alpha} : K(\alpha) \rightarrow K(\alpha)$ along the main diagonal, so $\text{Tr}_{L:K}(\alpha)=[L:K(\alpha)]\text{Tr}_{K(\alpha):K}\big(\alpha\big)$".
I understand the idea of constructing a basis for $L$ over $K$ in the manner they describe, but I do not understand at all where this 'block' matrix comes from. In fact, it seems to me that for any $\vec{l}\in L$, regardless of our choice of basis, we have
$$\alpha \text{I}_n\vec{l}=\alpha\vec{l}$$
where $\text{I}_n$ is the identity matrix of dimension $n$. So that $\text{Tr}_{L:K}(\alpha)=n\alpha$.
What am I getting wrong?
I think you're wrong.
If the minimal polynomial of $\alpha$ over $K$ is $f(x)=x^s+a_1x^{s-1}+\ldots+a_s$, then the basis $K(\alpha):K$ can be chosen as $1,\alpha,\ldots,\alpha^{s-1}$.
Let $u_1,\ldots,u_t$ be a basis of extension $L:K(\alpha)$.
Then the basis of $L:K$ is $\alpha_iu_j$, $0\leq i\leq s-1$, $1\leq j\leq t$.
On each block $u_j,\alpha u_j,\ldots,\alpha^{s-1}u_j$ of the basis, the linear transformation $m_\alpha$ acts as a shift $$ m_\alpha(u_j)=\alpha u_j,\ m_\alpha(\alpha u_j)=\alpha^2 u_j,\ \ldots, m_\alpha(\alpha^{s-1} u_j)=\alpha^s u_j=-(a_s+\ldots+\alpha^{s-1}a_1)u_j $$ Therefore the matrix $m_\alpha$ in this basis has a block form. On the diagonal there are $s\times s$-blocks of the form $$ \begin{pmatrix} 0&0&\ldots & -a_s\\ 1&0&\ldots &-a_{s-1}\\ 0&1&\ldots &-a_{s-2}\\ \ldots&\ldots&\ldots&\ldots\\ 0&0&\ldots&-a_1\end{pmatrix} $$ and there are $t$ blocks of this kind. It follows that $\operatorname{Tr}_{L:K}(m_\alpha)=-a_1t\in K$.
Addition. Your formula is correct in the following form $\operatorname{Tr}_{L:L}m_\alpha=\alpha$. But in this form it is of little interest. To define a trace over $K$, we must define the matrix of multiplication by $\alpha$ in a basis $L$ over $K$ and then the matrix coefficients necessarily lie in $K$, and hence the trace lies in $K$.
Edit. Corrected the matrix and formula for the trace. Thanks @Leo.