If we insist that (1) the degree of a composition is the product of degrees, and (2) the degree of an $n$-sheeted connected covering space is $n$, then there is a unique way to define the degree of $f:M\to N$ when $N$ is non-orientable.
If $f$ lifts to a map $\tilde{f}$, conditions (1) and (2) imply the degree of $f$ must be given by your formula $\deg(f)=2\deg(\tilde{f})$. In the case $f$ does not lift, we can form the fiber product $\tilde{M} := \tilde{N}\times_N M$, which will be a closed orientable manifold. Let $\pi_1:\tilde{M}\to \tilde{N}$, $\pi_2:\tilde{M}\to M$ be projection onto the first and second factor, respectively. Then $\varphi\circ\pi_1=\pi_2\circ f$, and by condition (2) we have $\deg(\pi_2)=\deg(\varphi)= 2$, so condition (1) implies $\deg(f)=\deg(\pi_1)$.
The answer is already briefly described in the comment:
First, one can show that there is $a\in \mathbb R$ such that
$$ \int_M f^* \omega = a \int_N \omega$$
for all top form $\omega$ on $N$. This is already non-trivial and is proved here.
Now we see that $a =\mathrm{deg}(f)$. Let $q\in N$ be a regular value of $f$. Then for each $p\in f^{-1}(q)$, there is an open set $U_p $ of $M$ so that $f|_{U_p} \to f(U_p)$ is a diffeomorphism onto an open set $V_p = f(U_p)$. Then $f^{-1}(p)$ is discrete, and thus is finite since $M$ is compact. Write $f^{-1}(q) = \{p_1, \cdots, p_k\}$.
Then one can find a local chart $(V, \psi)$ centered at $q$ and disjoint open subsets $U_1, \cdots, U_k$ of $M$ so that $f^{-1}(V) = U_1\cup\cdots \cup U_k$ and $f|_{U_i} : U_i \to V$ is a diffeomorphism for each $i=1, \cdots, k$.
Let $\omega$ be a bump form (see e.g. here) on $N$, compactly supported in $V$ and $\int_N \omega \neq 0$. Then $f^*\omega$ is supported in $f^{-1}(V)$ (see here) and thus
$$ \int_M f^*\omega = \int_{f^{-1}\ (V)} f^*\omega = \sum_i \int_{U_i} f^*\omega.$$
By the change of variable formula, since each $f|_{U_i}$ is a diffeomorphism,
$$ \int_{U_i} f^*\omega = \pm\int_V \omega $$
where $\pm$ depends if $df_{p_i} :T_{p_i}M \to T_qN$ is orientation preserving or reversing. Thus
$$ \int_M f^*\omega = \mathrm{deg}(f) \int_V\omega = \mathrm{deg}(f) \int_N \omega.$$
Since this is true for this $\omega$ and $\int_N \omega \neq 0$, $a=\mathrm{deg}(f)$ and thus the same holds for all top forms.
Best Answer
HINT: First of all, you can produce maps $S^n\to S^n$ of arbitrary degree $k\in\Bbb Z$, so it suffices to produce a map from $M$ to $S^n$ of degree $1$. Take a coordinate ball $B\subset M$. Using a bump function appropriately to make things smooth, map a sub-ball $B'\subset B$ diffeomorphically to $S^n-\{p\}$ and $M-B'$ to $p$.