For arbitrary subspaces $U,V$ of an arbitrary vector space $W$, we have the dimension formula
$$\dim U + \dim V = \dim (U+V) + \dim (U\cap V).$$
(Take a basis $B_1$ of $U\cap V$, and extend it by systems $B_2$ to a basis of $U$, and $B_3$ to a basis of $V$. Then $B_1 \cup B_2 \cup B_3$ is a basis of $U+V$.)
That yields the
$$\dim F + \dim F^\perp = \dim (F + F^\perp) + \dim (F\cap F^\perp)$$
part. It remains to see that $\dim F + \dim F^\perp = \dim E$. Let's denote the non-degenerate bilinear form by $\beta$. $\beta$ induces a linear map $\Phi \colon E \to E^\ast$ ($E^\ast$ is the dual space of $E$, the space of all linear maps $E\to K$) via
$$\Phi(x)(y) = \beta(x,y).$$
The non-degeneracy of $\beta$ is equivalent to the injectivity of $\Phi$. Since the spaces are finite-dimensional, we have $\dim E^\ast = \dim E$, and thus $\Phi$ is an isomorphism. For a subspace $F \subset E$, the image of $F^\perp$ under $\Phi$ is the annihilator of $F$,
$$\Phi(F^\perp) = F^0 = \{ \lambda \in E^\ast : F\subset \ker\lambda\}.$$
If you already know that $\dim F + \dim F^0 = \dim E$ for all subspaces of finite-dimensional spaces, that's it. Otherwise, to see that, choose a basis $B_0 = \{v_1,\dotsc, v_f\}$ of $F$, extend it to a basis $B = B_0 \cup B_1 = \{v_1,\dotsc,v_f,v_{f+1},\dotsc,v_e\}$ of $E$, and consider the dual basis $B^\ast = \{\lambda_1,\dotsc,\lambda_e\}$ of $E^\ast$, defined by
$$\lambda_i(v_j) = \delta_{ij} = \begin{cases}1 &, i = j\\ 0 &, i \neq j. \end{cases}$$
It is then easy to see that $F^0 = \operatorname{span} \{\lambda_{f+1},\dotsc,\lambda_e\}$, whence $\dim F^0 = e - f = \dim E - \dim F$.
For symmetric or skew-symmetric forms $(u,v)=0 \implies (v,u) = 0$. But you are right, the statement does not need any of them, just decide what $\perp$ means. The nice thing is that if non-degeneracy holds for one map, it holds for the flip one ( since, if a matrix is nonsingular, then its transpose also is). Here is a quick proof to have in your toolbox ( from Milnor&Husemoller's book Symmetric bilinear forms).
Take $v \in V$. The map $W \to F$, $u \mapsto (u,v) $ is a linear functional so it must be the dot product with a unique $w$ from $W$. Hence we have $v = w + (v - w)= w + w'$. Note that $w' \in W^{\perp}$.
Best Answer
You proved that : if $x\in W$ and $b_f(x,y) = 0$ for all $y\in V$, then $x=0$ (indeed, $f(x)=0$, so $x\in \ker f \cap W = 0$).
Now suppose the same holds only for $y\in W$; and let $z\in V$. Write $z=y+z'$ with $y\in W, z'\in \ker f$. What can you say about $b_f(x,z) $ ?
It follows that $b_{f\mid W\times W}$ is non-degenerate.
This amounts essentially to Omnomnomnom's comment, where they consider $V/\ker f$ instead of $W$ (in linear algebra over fields, quotients do essentially the same thing as complements)