The idea is that the possible outcomes in your sample are $i=1, \ldots, n$, and each outcome $i$ has equal probability $\frac{1}{n}$ (under the probability measure that assigns equal probability to all outcomes that you appear to be using). You have $n$ outcomes, not $n^2$.
To somewhat indulge your idea, you could compute:
$$ \operatorname{Cov}(X,Y) = \sum_i \sum_j (x_i - \mu_x) (y_j - \mu_y) P(X = x_i, Y = y_j )$$
Where:
- $P(X = x_i, Y = y_j) = \frac{1}{n}$ if $i=j$ since that outcome occurs $1/n$ times.
- $P(X = x_i, Y = y_j) = 0 $ if $i \neq j$ since that outcome doesn't or didn't
occur.
But then you'd just have:
$$ \sum_i \sum_j (x_i - \mu_x) (y_j - \mu_y) P(X = x_i, Y = y_j ) = \sum_i (x_i - \mu_x) (y_i - \mu_y) P(X = x_i, Y = y_i ) $$
Which is what the original formula is when $P(X = x_i, Y = y_i ) = \frac{1}{n}$.
You intuitively seem to want something like $P(X = x_i, Y = y_j ) = \frac{1}{n^2}$ but that is seriously wrong.
Simple dice example (to build intuition):
Let $X$ be the result of a roll of a single 6 sided die. Let $Y = X^2$.
Recall that a probability space has three components: a sample space $\Omega$, a set of events $\mathcal{F}$, and a probability measure $P$ that assigns probabilities to events. (I'm going to hand wave away the event stuff to keep it simpler.)
$X$and $Y$ are functions from $\Omega$ to $\mathcal{R}$. We can write out the possible values for $X$ and $Y$ as a function of $\omega \in \Omega$
$$ \begin{array}{rrr} & X(\omega) & Y(\omega) \\
\omega_1 & 1 & 1\\
\omega_2 & 2 & 4 \\
\omega_3 & 3 & 9 \\
\omega_4 & 4 & 16 \\
\omega_5 & 5 & 25 \\
\omega_6 & 6 & 36
\end{array}
$$
We don't have 36 possible outcomes here. We have 6.
Since each outcome of a die is equally likely, we have $P( \{ \omega_1) \}) = P( \{ \omega_2) \}) = P( \{ \omega_3) \}) = P( \{ \omega_4) \}) = P( \{ \omega_5)\}) = P( \{ \omega_6) \}) = \frac{1}{6}$. (If your die wasn't fair, these numbers could be different.)
What's the mean of $X$?
\begin{align*}
\operatorname{E}[X] = \sum_{\omega \in \Omega} X(\omega) P( \{ \omega \} ) &= 1 \frac{1}{6} + 2\frac{1}{6} + 3 \frac{1}{6} + 4 \frac{1}{6} + 5 \frac{1}{6} + 6 \frac{1}{6}\\
&= \frac{7}{2}
\end{align*}
What's the mean of $Y$?
\begin{align*}
\operatorname{E}[Y] = \sum_{\omega \in \Omega} X(\omega) P( \{ \omega \} ) &= 1 \frac{1}{6} + 4\frac{1}{6} + 9 \frac{1}{6} + 16 \frac{1}{6} + 25 \frac{1}{6} + 36 \frac{1}{6}\\
&= \frac{91}{6}
\end{align*}
What's the covariance of $X$ and $Y$?
\begin{align*}
\sum_{\omega \in \Omega} \left(X(\omega) - \frac{7}{2}\right)\left( Y(\omega) - \frac{91}{6}\right) P( \{ \omega \} ) &= \left( 1 - \frac{7}{2} \right)\left( 1 - \frac{91}{6} \right) P(\{\omega_1\}) + \left( 2 - \frac{7}{2} \right)\left( 4 - \frac{91}{6} \right) P(\{\omega_2\}) + \left( 3 - \frac{7}{2} \right)\left( 9 - \frac{91}{6} \right) P(\{\omega_3\}) + \left( 4 - \frac{7}{2} \right)\left( 16 - \frac{91}{6} \right) P(\{\omega_4\}) + \left( 5 - \frac{7}{2} \right)\left( 25 - \frac{91}{6} \right) P(\{\omega_5\}) + \left( 6 - \frac{7}{2} \right)\left( 36 - \frac{91}{6} \right) P(\{\omega_6\}) \\
&\approx 20.4167
\end{align*}
Don't worry about the arithmetic. The point is that to calculate $\operatorname{Cov}\left(X , Y\right) = \operatorname{E}\left[(X -\operatorname{E}[X])(Y - \operatorname{E}[Y]) \right] = \sum_{\omega \in \Omega} \left(X(\omega) - \operatorname{E}[X]\right)\left( Y(\omega) - \operatorname{E}[Y]\right) P( \{ \omega \} ) $ you sum over the 6 possible outcomes $\omega_1, \ldots, \omega_6$.
Back to your situation...
The possible outcomes in your sample are $i=1\, \ldots, n$. Those are the outcomes you should sum over.
