Bound covariance of two discrete random variables
This follows from Pinsker's inequality. The inequality states that for any two distributions (here, discrete) $P$, and $Q$, it holds that

$$\|P-Q\| \le \sqrt{2D_{\text{KL}}(P\|Q)} $$
where $D_{\text{KL}}(\cdot \|\cdot)$ is the Kullback–Leibler divergence and $|P-Q|$ is their total variation.

For the right-hand side, recall that for any $X,Y$ random variables with joint distribution $p_{x,y}(x,y)$ and marginals $p_x(x)$, $p_y(y)$, we have
$$I(X,Y) = D_{\text{KL}}(p_{x,y} \| p_x p_y).$$

So if we define $P = p_{x,y}$ and $Q=p_xp_y$, we obtain the desired right-hand side.

On the other hand, by definition,
$$
\begin{align}
\| P - Q\| &amp; = \sum_{x,y}|p(x,y) - p_x(x)p_y(y)| \\
&amp; \ge \sum_{x,y}|p(x,y) - p_x(x)p_y(y)| \cdot xy \\
&amp; = \sum_{x,y}|p(x,y)xy - p_x(x)x\cdot  p_y(y)y|\\
&amp; \ge \left|\sum_{x,y} \left(p(x,y)xy - p_x(x)x\cdot  p_y(y)y\right)\right|\\
&amp; = \left|E[XY] - E[X]E[Y]\right| \\
&amp;= |\text{cov}(X,Y)|.
\end{align}
$$
The first equality follows since $x,y \in [0,1]$ and each term is non-negative. The rest of the derivation is mostly algebra. I'm probably missing a factor 2 of the normalization of the total variation. This will give the right constant inside the square root.