$E=mc^2$ resembles non-relativistic kinetic energy formula $E_K = \frac{1}{2}mv^2$?

In short, no, it is not a coincidence, they are related. Namely, you may derive the kinetic energy as the first order approximation to the relativistic energy.

We have,

$$ E_0 = mc^2 $$

as you say correctly. Then

$$ E = \gamma m c^2 = \left( 1 - \frac{v^2}{c^2}\right)^{-\frac{1}{2}} m c^2 $$

or using a binomial expansion

$$ E \simeq \left( 1 + \frac{1}{2} \frac{v^2}{c^2} + \dots \right) m c^2 \simeq mc^2 + \frac{1}{2} mv^2 $$

So subtacting the rest energy $E_0$ we get

$$ E_k = E - E_0 \simeq \left( mc^2 + \frac{1}{2} mv^2 \right) - \left( mc^2 \right) = \frac{1}{2} m v^2$$

Note that we can of course only use this expansion when $v \ll c$. This makes sense, because that is exactly the case in Newtonian mechanics, which is where we use the more familiar kinetic energy formula.

Every relationship between mass and energy will contain two factors of velocity, for dimensional consistency.

In special relativity we have the more exact relationship $$ E^2 - p^2c^2 = m^2c^4 $$ where the momentum $p$ is $$ p = \frac{mv}{\sqrt{1-v^2/c^2}}. $$ You can do a little algebra to show that the total energy is always $$ E = \frac{ mc^2}{\sqrt{1-v^2/c^2}}. $$

In mathematics we have a tool called the "binomial theorem," which tells us that $$ (1+\epsilon)^n = 1 + n\epsilon + \frac{n(n-1)}{2!}\epsilon^2 + \cdots $$ This expression turns out to hold even if the power $n$ is not a positive integer! If $\epsilon\ll1$, we also have the luxury of being able to throw away the higher powers. For small speeds, then, the Einstein equation becomes $$ E = \frac{ mc^2}{\sqrt{1-v^2/c^2}} = mc^2 + mc^2 \cdot \frac{-1}{2}\frac{-v^2}{c^2} + mc^2 \cdot\mathcal O\left( (v/c)^4 \right) $$ which is clearly the rest energy, the classical kinetic energy, and a relativistic correction that becomes large when $v\approx c$.