L-infinity-norm regularized proximity problem

This is indeed a classic problem. Recall the more general problem of computing the prox operator of an lsc convex function $f$, i.e., \begin{equation*} \text{prox}_f(y) := \operatorname{argmin}\quad \tfrac12\|x-y\|^2 + f(x). \end{equation*} For this prox operator, we have the well-known Moreau decomposition \begin{equation*} \text{Id} = \text{prox}_f + \text{prox}_{f^*}, \end{equation*} where $f^*$ denotes the Fenchel conjugate of $f$. In your case, $f(x)=\lambda \|x\|_{\infty}$, whose conjugate is the indicator function for the constraint $\|x\|_1 \le \lambda$. Thus, you can alternatively solve the optimization problem \begin{equation*} \min\quad \tfrac12\|x-y\|^2\quad\text{s.t.}~~\|x\|_1 \le \lambda. \end{equation*} This is the projection onto the $\ell_1$-ball, which is an extensively well-studied problem. I would recommend this paper by L. Condat, which gives a more recent summary of this classic problem (dates to the 1950s), and to a few existing methods while providing some additional context (also, you can find C code at this link from L. Condat's webpage).