Yes. You can run rank-revealing QR on your matrix $A$, which will stop at step $k$ (hence effectively terminating in $O(mnk)$) and produce $A = QRP$, where $R$ has nonzeros only in its first $k$ rows, and $Q,P$ are orthogonal. You can now compute and SVD of $R$, and use it to piece back the factors with a few matrix products with cost $O(\max(m,n)k^2)$.
LAPACK has an implementation of the svd of a 2x2 triangular matrix. It appears to be very robust.
The routine is XLASV2.
To apply to a regular 2x2 matrix, you can simply apply a single givens rotation from the left/right.
Using the Cholesky decomposition is the quickest way I know of checking if a symmetric matrix has negative eigenvalues. Nothing wrong with that. Plus, if it succeeds, you already have the Cholesky decomposition! Of course, if there are any negative eigenvalues, it will fail. You will not need to check the entries of $L$.
Cholesky factorization is for symmetric positive definite matrices, and it will fail if the matrix has negative eigenvalues. You should use singular value decomposition for that purpose, or maybe a QR algorithm would suffice if you just need some of the eigenvalues.
Edit 1: Of course, I should also add that, in general, L would not give you much information ...
I was able to reproduce your initial result via the snippet. However, by adding some more options to your svd call:
[Uk, Sk, Vk] = svds(A,k,'largest','display',true);
we see that the algorithm indeed changes to a dense one (@ThijsSteel).
For 300 singular values:
=== Singular value decomposition A*v = sigma*u, A'*u = sigma*v ===
Computing 300 largest ...