Composition of pseudo-differential operators
I realized that the following theorem is quite helpful to prove the statement:
Theorem For all $N>0$ there exists $N_1 \in \mathbb{N}_0$ such that $T_{N_1} \in S^{-N}$,$$p(\cdot,D) \circ q(\cdot,D)- \sum_{|\alpha| \leq N_1} \tau_{\alpha}(\cdot,D) = T_{N_1}(\cdot,D)$$ where $$\tau_{\alpha}(x,\xi) := \frac{1}{\alpha!} \cdot \partial_\xi^{\alpha} p(x,\xi) \cdot D_x^{\alpha}q(x,\xi)$$
In particular, by choosing $N=\max\{|m_1+m_2|,1\}$, I obtain $$p(\cdot,D) \circ q(\cdot,D) = T_{N_1}(\cdot,D)+\sum_{|\alpha| \leq N_1} \tau_{\alpha}(\cdot,D)$$ where $T_{N_1} \in S^{-\max\{|m_1+m_2|,1\}} \subseteq S^{m_1+m_2}$ (note that $S^{r_1} \subseteq S^{r_2}$ for $r_1 \leq r_2$). Moreover, using the definition of $\tau_{\alpha}$, one can easily show that $\tau_{\alpha} \in S^{m_1+m_2-|\alpha|}$ for $\alpha \in \mathbb{N}_0^n$: $$\begin{align} \partial_\xi^{\gamma} \tau_{\alpha}(x,\xi) &= \frac{1}{\alpha!} \sum_{\gamma_1+\gamma_2=\gamma} c_{\gamma_1,\gamma_2} \partial_\xi^{\alpha+\gamma_1} p(x,\xi) \cdot D_x^{\alpha} \partial_\xi^{\gamma_2} q(x,\xi) \\ \Rightarrow |\partial_\xi^{\gamma} \tau_{\alpha}(x,\xi)| &\leq \frac{1}{\alpha!} \cdot \sum_{\gamma_1+\gamma_2=\gamma} c_{\gamma_1,\gamma_2} (1+|\xi|)^{m_1-|\alpha|-|\gamma_1|} \cdot (1+|\xi|)^{m_2-|\gamma_2|} \\ &\leq c \cdot (1+|\xi|)^{(m_1+m_2-|\alpha|)-|\gamma|} \end{align}$$ for all $\gamma \in \mathbb{N}_0^n$. Similar proof works for derivative with respect to $x$.
Thus $p(\cdot,D) \circ q(\cdot,D)$ has a symbol in $S^{m_1+m_2}$ since the operator can be represented as finite sum of operators with symbols in $S^{m_1+m_2}$.