I believe that this 'relaxed' definition gives the same minimal key length as the standard perfect security definition; that is, the number of keys $|K|$ must be at least as large as the number of possible plaintexts $|P|$. This is true for any $\epsilon < 1$.
Suppose we had a set of keys that was smaller than the number of plaintexts, or $|K| < |P|$. In that case, we pick a possible ciphertext $c$ and see that can be decrypted to at most $|K|$ distinct plaintexts (depending on the key); hence there must be a plaintext $p_0$ that it cannot decrypt to. Let us call plaintext $p_1$ a plaintext that it can decrypt to.
Then, consider the probability distribution:
$M = p_0$ with probability $\epsilon$
$M = p_1$ with probability $1 - \epsilon$
$M$ is any other plaintext with probability 0
If we consider the equation with $m = p_0$, we have:
$Pr[ M = m | C = c ] = 0$ (because that plaintext is impossible with that ciphertext)
$Pr[ M = m ] = \epsilon$
And hence $|Pr[M=m|C=c] - Pr[M=m]| = \epsilon \not< \epsilon$, and so we find that the required inequality does not hold.
Hence, that relation can hold in general only if $|K| \ge |P|$, which is the same bound as what perfect secrecy requires.