Indeed, there is also a bound $\|P-Q\| \lesssim \alpha$.

There are certainly many other more involved and elegant proofs, but here is a very basic one. As noticed in the comments, we can assume that the $e_i$ span a dense subspace, in which case we have to prove that $\|Q-Id\|\lesssim \alpha$. In other words that for every $x = \sum_i \lambda_i e_i$ in the linear span, we have $\|Qx-x\| \lesssim \alpha \|x\|$.

The right-hand side is equal to the square root of
$ \sum_{i,j} \lambda_i \overline{\lambda_j} \langle e_i,e_j\rangle$,
so by the assumption and Cauchy-Schwarz we get
$$ |\|x\|^2 - \sum_i |\lambda_i|^2 |\leq \alpha \sum_{k \in \mathbb Z} e^{-|k|} \sum_i |\lambda_i \lambda_{i+k}| \leq \alpha \sum_{k \in \mathbb Z} e^{-|k|} \sum_i |\lambda_i|^2.$$

So for $\alpha$ small enough we have
$$ \|x\| \lesssim (\sum_i |\lambda_i|^2)^{\frac 1 2} \lesssim \|x\|.$$

Similarly, $Qx-x= \sum_{i,j} \lambda_i (\langle e_i,e_j\rangle e_j - \delta_{i,j}) e_j$, so by the preceding inequality for $Qx-x$,
$$\|Qx-x\| \simeq (\sum_{j} |\sum_i \lambda_i(\langle e_i,e_j\rangle - \delta_{i,j})|^2)^{\frac 1 2} \lesssim \alpha (\sum_{j,s,t} |\lambda_s \lambda_{t}| e^{-|s-j|-|t-j|})^{\frac 1 2}.$$
Bound $\sum_j e^{-|s-j|-|t-j|} \lesssim e^{-|s-t|/2}$. You obtain
$$ \|Q_x-x\|\lesssim \alpha (\sum_{s,t} |\lambda_s\lambda_t| e^{-|s-t|/2})^{\frac 1 2} \lesssim \alpha (\sum_i |\lambda_i|^2)^{\frac 1 2}.$$
This is $\lesssim \alpha \|x\|$ by the first computation.

3more comments