I'd like to thank Jordan Payette for the crucial help.
Locally, $R_\phi$ is represented by points $(x,(d\phi)^*\eta,\phi(x),\eta)$, hence it is parametrized by coordinates $x,\eta$. This proves that $R_\phi$ is embedded in $T^*Q_1\times T^*Q_2$ and has dimension $n_1+n_2$ (i.e., half the dimension of the ambient space). So in order to prove that $R_\phi$ is Lagrangian, it suffices to show that it is isotropic, i.e., $i^*\omega=0$, where $i:R_\phi\hookrightarrow T^*Q_1\times T^*Q_2$ with $ (x,\eta)\mapsto (x,(d\phi)^*\eta,\phi(x),\eta)$ is the inclusion.
If $u(x,\eta):=(d\phi)_x^*(\eta)$, notice that:
\begin{align*}
u_i&=u(x,\eta)\left(\frac{\partial}{\partial x_i}\right)=\eta\left(d\phi\left(\frac{\partial}{\partial x_i}\right)\right)=\sum_{j=1}^{n_2}\eta_j\frac{\partial \phi_j}{\partial x_i}\\
\frac{\partial u_i}{\partial x_k}-\frac{\partial u_k}{\partial x_i}&=\sum_{j=1}^{n_2}\eta_j\frac{\partial^2 \phi_j}{\partial x_k\partial x_i}-\eta_j\frac{\partial^2 \phi_j}{\partial x_i\partial x_k}=0\\
\frac{\partial u_i}{\partial \eta_k}&=\frac{\partial \phi_k}{\partial x_i}
\end{align*}
Hence:
\begin{align*}
i^*\omega &=i^*\left(\sum_{i=1}^{n_1}dx_i\wedge d\xi_i-\sum_{j=1}^{n_2}dy_j\wedge d\eta_j\right)\\
&=\sum_{i=1}^{n_1}dx_i\wedge du_i-\sum_{j=1}^{n_2}d\phi_j\wedge d\eta_j\\
&=\sum_{i=1}^{n_1}dx_i\wedge\left(\sum_{k=1}^{n_1}\frac{\partial u_i}{\partial x_k}dx_k+\sum_{j=1}^{n_2}\frac{\partial u_i}{\partial\eta_j}d\eta_j\right)-\sum_{j=1}^{n_2}\left(\sum_{i=1}^{n_1}\frac{\partial\phi_j}{\partial x_i}dx_i\right)\wedge d\eta_j\\
&=\sum_{i=1}^{n_1}\sum_{k=1}^{n_1}\frac{\partial u_i}{\partial x_k}dx_i\wedge dx_k+\sum_{i=1}^{n_1}\sum_{j=1}^{n_2}\underbrace{\left(\frac{\partial u_i}{\partial\eta_j}-\frac{\partial\phi_j}{\partial x_i}\right)}_{=0}dx_i\wedge d\eta_j\\
&=\sum_{1\leq i<k\leq n_1}\underbrace{\left(\frac{\partial u_i}{\partial x_k}-\frac{\partial u_k}{\partial x_i}\right)}_{=0}dx_i\wedge dx_k=0
\end{align*}
We prove that $R_\phi$ is diffeomorphic to $N^*\Gamma_\phi$, where $\Gamma_\phi:=\text{graph}(\phi)$. If $i':\Gamma_\phi\hookrightarrow Q_1\times Q_2$ with $x\mapsto (x,\phi(x))$ is the inclusion, we have $di'\left(\frac{\partial}{\partial x_i}\right)=\frac{\partial}{\partial x_i}+d\phi\left(\frac{\partial}{\partial x_i}\right)$, which means $T_{(x,\phi(x))}\Gamma_\phi=\text{span}\left(\frac{\partial}{\partial x_i}+d\phi\left(\frac{\partial}{\partial x_i}\right)\right)$. Moreover, $T^*(Q_1\times Q_2)\simeq T^*Q_1\times T^*Q_2$ and $N^*\Gamma_\phi=\{(x,\xi)\in T^*(Q_1\times Q_2)\mid x\in \Gamma_\phi,\,\xi|_{T_x\Gamma_\phi}\equiv 0\}$. Therefore:
\begin{align*}
N^*\Gamma_\phi &\simeq\{(x,\xi,y,\eta)\mid (x,y)\in \Gamma_\phi,\,(\xi,\eta)|_{T_{(x,y)}\Gamma_\phi}\equiv 0\}\\
&=\left\{(x,\xi,y,\eta)\mid y=\phi(x),\,\xi\left(\frac{\partial}{\partial x_i}\right)+\eta\left(d\phi\left(\frac{\partial}{\partial x_i}\right)\right)=0\,\forall i\right\}\\
&=\left\{(x,\xi,y,\eta)\mid y=\phi(x),\,(\xi+(d\phi)^*\eta)\left(\frac{\partial}{\partial x_i}\right)=0\,\forall i\right\}\\
&=\{(x,\xi,y,\eta)\mid y=\phi(x),\,\xi=-(d\phi)^*\eta\}\subset T^*Q_1\times T^*Q_2
\end{align*}
Since $f:(x,\xi,y,\eta)\mapsto (x,\xi,y,-\eta)$ is a diffeomorphism (in fact a symplectomorphism) from $(T^*Q_1\times T^*Q_2,\omega_1\oplus\omega_2)$ to $(T^*Q_1\times T^*Q_2,\omega_1\oplus-\omega_2)$, we get a diffeomorphism:
$$\left.f\right|_{N^*\Gamma_\phi}:N^*\Gamma_\phi\to R_\phi$$
The sub-assertion
... the normal bundle of $S$ in $M$ and the normal bundle of $S$ in $f(S \times \mathbb R^{n-k})$ are the same...
is false as stated literally. They aren't the "same". But it contains a grain of truth which you can then use to turn into a proof.
The key thing to keep in mind is that whenever you are tempted to use the "s" word, you should instead ask yourself: What kind of isomorphism are we talking about here?
The true statement which you should have in place of the one above is
... the derivative $Df : T(S \times \mathbb R^{n-k}) \to TM$ restricts to an isomorphism between the normal bundle of $S \times 0$ in $S \times \mathbb R^{n-k}$ and the normal bundle of $f(S \times 0)$ in $M$...
And now you can go on to prove it.
Best Answer
In general, given a vector bundle $\pi:B\to M$ and an embedded submanifold $S\subseteq M$, one can define the restricted bundle as $R=\pi^{-1}(S)$, with the projection given by $\pi|_R:R\to S$. This is also a vector bundle. This restriction can also be defined as the pullback bundle $R=\iota^*B$ where $\iota:S\to M$ is the inclusion map.
To your second qustion, the answer is yes; this can be seen by noting that, for $p\in C$, we have the decompositions $T_pM=T_pP\oplus N_pP$ and $T_pP=T_pC\oplus N_pC$ where $N_pC$ denotes the normal space w.r.t. $P$.