We only need to consider the case in which the graph is connected and number of edges is even. We hence assume the above conditions once for all.
As a first observation, notice that if the graph is a star then it can easily be partitioned.
You can then show by induction that other graphs can also be partitioned. The induction is on the number $m$ of edges.
If the graph has $0$ edges then the claim is trivial.
Consider an even value of $m>0$. If $G$ is a star we are done.
Otherwise, since graph has at least $2$ edges, and we can compute an arbitrary rooted spanning tree $T$. Let $u$ be the deepest leaf of $T$. If there are multiple choices for $u$ prefer a vertex that has at least one incident non-tree edge.
Let $v$ be $u$'s parent, and let $w$ be $v$'s parent (if any).
If $u$ has at least $2$ incident non-tree edges, then select and remove them.
Otherwise, if $u$ has exactly $1$ incident non-tree edge $e$, select and remove the path containing $e$ and $(u,v)$.
Otherwise, if $v$ has at least $1$ incident non-tree edge $e$, select and remove the path containing $e$ and $(u,v)$.
In the only remaining case neither $u$ nor $v$ have incident non-tree edges. Moreover $w$ exists, since otherwise $v$ would be the root $T$, $T$ would have height $1$, and no child of $v$ would have any incident non-tree edge, implying that $T$ is a star. Select remove the path containing $(u,v)$ and $(v,w)$.
Ignore any vertex whose degree has been reduced to $0$. The remaining graph has $m-2 \ge 0$ edges, and the claim follows by invoking the induction hypothesis.
The above proof immediately leads to a liner-time algorithm once you observe that the spanning tree of the graph needs to be computed only once.