There's a relatively simple answer if you know about eigenvalue interlacing for Hermitian Matrices. You can simplify this by exploiting the fact that singular values are all real non-negative.
Since $B:=\bigg[\begin{array}{c|c|c|c|c}A & \mathbf z_m \end{array}\bigg]$, we have
$BB^* = AA^* + \mathbf z_m\mathbf z_m^*$
(use the outer product formulation of matrix multiplication to confirm this)
This has eigenvalues
$\gamma_{m}\leq \gamma_{m-1}\leq ... \leq \gamma_1$
The eigenvalues of a Hermitian matrix interlace with that of a rank-one PSD Hermitian update to said matrix. So we have
$\lambda_{m}\leq \gamma_{m}\leq \cdots \leq \lambda_{n+1}\leq \gamma_{n+1}\leq \lambda_n \leq \gamma_n\leq \cdots \leq \gamma_{m-1}\leq ...\lambda_1\leq \gamma_1$
taking square roots
$\lambda_1 \leq \gamma_1 \implies \sigma_1 (A)\leq \sigma_1 (B)$ and
$\gamma_{n+1}\leq \lambda_n\implies \sigma_{n+1}(B) \le \sigma_n (A)$
Footnote:
the non-zero singular values of an $m\times n$ matrix $Y$ are the given by the square roots of the non-zero eigenvalues of $YY^*$ or $Y^*Y$. Conventions vary somewhat but given that $A$ is tall and skinny we have $A=U\Sigma V^*$ with square (unitary) $U$ and $V$ with $\Sigma$ being $m\times n$ and thus having exactly $n$ elements on its diagonal -- i.e. $n$ singular values. Running essentially the same argument on $B$ tells us that it has exactly $n+1$ singular values. Thus values like $\lambda_m$ must be zero and don't directly map to singular values of $A$ -- they are 'filler'. A different way to finish this then is to take
$\lambda_{m}\leq \gamma_{m}\leq \cdots \leq \lambda_{n+1}\leq \gamma_{n+1}\leq \lambda_n \leq \gamma_n\leq \cdots \leq \gamma_{m-1}\leq ...\lambda_1\leq \gamma_1$
and observe that $AA^*$ and $A^*A$ have the same non-zero eigenvalues (and the same for $BB^*$ and $B^*B$) so checking dimensions this implies
$\gamma_{n+1}\leq \lambda_n \leq \gamma_n\leq \cdots \leq \gamma_{m-1}\leq ...\lambda_1\leq \gamma_1$
for the eigenvalues of $B^*B$ and $A^*A$ respectively. The square roots of these give the singular values of $B$ and $A$.