Can we approximate any eigenvalue of an infinite matrix via eigenvalues of some sequence of submatrices which approximates the matrix?
This is not a full answer but maybe an idea or a rough roadmap on how to approach this problem (and also it's too long for a comment).
First consider $T\in\mathcal K(\ell_2)$ (compact linear operator on $\ell_2$) where $T$ is triangular, i.e. there exists an orthonormal basis $(g_n)_{n\in\mathbb N}$ of $\ell_2$ such that the infinite matrix $T_g:=(\langle g_j,Tg_k\rangle)_{j,k\in\mathbb N}$ is either upper or lower triangular. For such an operator, it is known that the non-zero eigenvalues of $T$ are exactly the diagonal entries of $T_g$. More precisely, $$ \sigma(T)\setminus\lbrace 0\rbrace = \lbrace \langle g_j,Tg_j\rangle\,|\,j\in\mathbb N\rbrace\setminus\lbrace 0\rbrace $$ refer to Theorem A.7 in this paper (or Thm.4.2 in the respective arXiv-version). W.l.o.g. let $T$ be upper triangular. Now if one defines $$ T_{g,n}=\sum\nolimits_{a,b=1}^n\langle g_a,Tg_b\rangle\langle g_b,\cdot\rangle g_a=\begin{pmatrix} \langle g_1,Tg_1\rangle&\cdots&\cdots&\langle g_1,Tg_n\rangle\\0 &\ddots&&\vdots\\\vdots&\ddots&\ddots&\vdots\\0&\cdots&0&\langle g_n,Tg_n\rangle\end{pmatrix}\oplus 0 $$ as the embedded upper left $n\times n$ block of $T$ w.r.t. the basis in which $T$ is triangular then, evidently, the eigenvalues of $T_{g,n}$ converge to the eigenvalues of $T$ in the sense that the eigenvalue sequence $\lambda_{g,n}$ (of $T_{g,n}$) converges to the eigenvalue sequence $\lambda$ (of $T$) in the $\ell^\infty$-norm.
Problem 1. Does this statement still hold for triangular $T\in\mathcal K(\ell_2)$ if $T_{g,n}$ is replaced by the block approximation $T_{f,n}$ with respect to an arbitrary orthonormal basis $(f_n)_{n\in\mathbb N}$ of $\ell_2$?
Unlike in finite dimensions, there is no Schur triangulation for arbitrary operators if the underlying Hilbert space is infinite-dimensional (not even for compact operators). However, one still has the following similar result, cf. Lemma 16.28 in "Introduction to Functional Analysis" by Meise & Vogt (1997):
For $T\in\mathcal K(\ell_2)$ there exists an orthogonal decomposition $\ell_2=\mathcal H_0\oplus \mathcal H_1$ and an orthonormal basis $(g_j)_{j\in M}$ of $\mathcal H_0$ (where $M$ can be finite or infinite and corresponds to the non-zero eigenvalues of $T$) such that, roughly speaking, $$ T=\begin{pmatrix} T_{0,0}&T_{0,1}\\0&T_{1,1}\end{pmatrix}\,. $$ Here, $T_{0,0}$ is upper triangular w.r.t. $(g_j)_{j\in M}$ and $\sigma(T_{1,1})=\lbrace 0\rbrace$.
Problem 2. Is this construction / this idea enough to extend the above result to arbitrary compact operators ("There exists an orthonormal basis of $\ell_2$ such that the eigenvalue sequence of ...")?
This might boil down to the question on if and how one can control the eigenvalues when taking out blocks from the Volterra part $T_{1,1}$ of $T$. Similar to Problem 1, the following question arises naturally:
Problem 3. If Problem 2 has a positive answer, does it even hold for any orthonormal basis of $\ell_2$?
I can't really answer this, but I have an observation/analysis which convinced me, that in the following example the eigenvalues of an infinite matrix (matrix-operator) are (should be) complex, but the eigenvalues of all truncated matrixes with arbitrary truncation-size are always real and some of them growing to infinity by increasing the truncation-size. Perhaps the answer of @FrederikVomEnde and especially his references contains everything needed here, but I'm not expert enough to judge this. In this case take my answer just as an illustration by a nontrivial example.
This seems to be the case for "Carleman-matrices" for the function $f(x)=b^x$ with $b \gt \exp(\exp(-1)) $ (in the discussions in the tetration-forum this number is often called $\eta$)
There is a conjugacy-operation, which for finite matrices would be a similarity transformation which preserves there the eigenvalues, and which I think should be as well valid with the same property for the infinite matrix. Note, that this is nothing else than reflecting the "Schroeder-function" for the function $f(x)$ , when its power series is shifted to its complex fixpoint. ($g(x)=f(x+t)-t$ where $t$ is the fixpoint)
The result of this shifting is a formal power series with complex coefficients and complex eigenvalues, and -taking this in the view of Carleman-matrices- the according "similarity transformation" produces an infinite Carleman matrix with complex entries which is triangular and has complex eigenvalues.
A matrix-formula would look like this:
Denote the Carlemanmatrix for $f(x)$ by $F$ and the matrix performing a similarity-transform $P(t)$ and the remaining core-matrix $G$ which is the Carleman-matrix associated to function $g(x)$
$$ G = P(t) \cdot F \cdot P(t)^{-1}$$
where $P(t)$ and $G$ are triangular. Here the eigenvalues of $G$ should be equal to that of $F$, but are complex-valued if $b \gt \eta$ and thus the fixpoint $t$ is complex itself.
However, each truncation (from the upper-left edge of $F$) instead of the similarity-transformation gives a finitely-sized Vandermonde-style matrix, and this matrices have real eigenvalues, whose maximal value grows quadratically(?) with the truncation-size towards $\infty$ but not towards complex values.
So increasing the truncation-size should thus never produce convergence towards the eigenvalues of $F$.
(If we look at $f(x)$ for some $b$ in the range $1<b<\eta$ then we get a carleman-matrix which can be similarity-transformed by real-valued matrix-factors (representing function-conjugacy towards a real fixpoint) and whose triangular core-matrix has also real values and real eigenvalues).
Remark: I've not yet come at a formal and rigorous statement and/or analysis of this so far, so I've to give this as a hypothese, for which I've however much evidence.
Today I by chance came across Chapter XI.9 of the Dunford & Schwartz classic "Linear operators. Part II. Spectral theory", and Lemma 5 in said chapter reads as follows:
Let $T_n,T$ be compact operators, and let $T_n\to T$ in the uniform operator topology. Let $\lambda_m(T)$ be an enumeration of the non-zero eigenvalues of $T$, each repeated according to its multiplicity. Then there exist enumerations $\lambda_m(T_n)$ of the non-zero eigenvalues of $T_n$, with repetitions according to multiplicity, such that $$ \lim_{n\to\infty}\lambda_m(T_n)=\lambda_m(T),\qquad m\geq 1, $$ the limit being uniform in $m$.
As you correctly observed the finite truncations $T_n$ converge to $T$ in norm ${}^1$ so the eigenvalue approximation property you were interested in holds.
${}^1$: For anyone who wants to see why that is: in separable Hilbert spaces, such as $\ell^2$, finite-dimensional projections $\Pi_n:=\sum_{i=1}^n\langle e_i,\cdot\rangle e_i$ converge to the identity in the strong operator topology (simple consequence of Bessel's inequality) so compactness of $T$ ensures $T_n=\Pi_nT\Pi_n\to T$ in norm (see, e.g., Proposition 2.1 in this article by Widom).