I copy'n'paste the solution from problem 5 at http://www.imomath.com/index.php?options=543&lmm=0 ---
The answer is no. Assume that, on the contrary it is possible to partition a polygon $P$ into non-convex quadrilaterals. Let $n$ be the number of quadrilaterals. Denote by $S$ the total sum of all internal angles of all the quadrilaterals. Since the sum of internal angles of each quadrilateral is $360^\circ$ we have $S=360^\circ n$. However, each of the nonconvex angles has to be in the interior of $P$, hence the sum of angles around the vertex of that angle has to be $360^\circ$. This immediately gives $360^\circ n$ as the sum of angles around such vertices. Since those are not the only vertices (at least the vertices of $P$ will contribute to the sum $S$), we have that $S\gt360^\circ n$ and this is a contradiction.
Just for fun, I made a little animation of the half-convex example linked to by @Alexander Schmeding. The upper half is an ellipse with minor-to-major axis ratio ranging from $b = 1/2$ to $b = \sqrt{2}$. The curve can be parametrized as $$f_b(\theta) = \begin{cases} (\cos \theta, b \sin \theta), & 0 \le \theta \le \pi, \\ {\displaystyle \frac{2 (b \cos \theta, \sin \theta)}{\sqrt{b^2 \cos^2 \theta + \sin^2 \theta}}} - (\cos \theta, b \sin \theta), & \pi < \theta \le 2\pi. \end{cases}$$ In Mathematica, we can generate an interactive plot with
F[t_, b_] := Piecewise[{{{Cos[t], b Sin[t]}, 0 <= t < Pi},
{2 {b Cos[t], Sin[t]}/Sqrt[(b Cos[t])^2 + Sin[t]^2]
- {Cos[t], b Sin[t]}, Pi <= t <= 2 Pi}}]
Manipulate[Show[ParametricPlot[F[t, b], {t, 0, 2 Pi},
PlotRange -> {{-1, 1}, {-1.5, 1.5}}, PlotStyle -> Black],
Graphics[Flatten[{Opacity[0.5], {Hue[#/Pi],
Line[{F[#, b], F[# + Pi, b]}]} & /@ (Range[n] Pi/n)}]]]
{{b, 1}, 1/2, Sqrt[2]}, {n, 1, 75, 1}]
And we get this:
What I found really interesting is how the curve looks like it's the same near the extremes of the animation, but it obviously isn't so from the definition of $f$ itself. Bonus points if you can parametrize the envelope of normals for $b \in [1/2, \sqrt{2}]$. And more bonus points if you can compute the enclosed area.
Best Answer
The statement is false. Consider this polygon on eight sides:
Suppose we colour the vertices of any even-sided polygon black or white. Then it is easy to see that any quadrilateration (decomposition by diagonals into quadrilaterals), if it exists, must use diagonals connecting vertices of opposite colours. Yet the only diagonals lying wholly within this polygon are the edges between the inner square of vertices, the latter of which must all have the same colour. Thus no quadrilateration is possible.
A similar construction shows that such indecomposable polygons exist for any even number of sides greater than 4.