$\newcommand{\De}{\Delta} \newcommand{\ep}{\epsilon} \newcommand{\vp}{\epsilon}$
Here is yet another answer providing the exact bound. This answer is perhaps a bit more elementary than the excellent answer given by user Algernon. To preserve the history of the question, I have also retained my previous answer, which used different (if somewhat similar) ideas and provided a suboptimal bound.
Note that, with the convention $p\ln p:=0$ for $p=0$, the difference \begin{equation} \De:=\sum_1^N p_i\ln p_i-\sum_1^N q_i\ln q_i \end{equation} between the entropies of $Q=(q_i)_{i=1}^N$ and $P=(p_i)_{i=1}^N$ is continuous in $P,Q$ and hence attains a maximum at some point $(P,Q)$ subject to the given conditions. In what follows, $(P,Q)$ is such a extremal point, unless specified otherwise. Without loss of generality (wlog), for some $k\in\{1,\dots,N\}$ we have $p_i\ge q_i$ for $i\le k$, $p_i\le q_i$ for $i\ge k+1$, $q_1\ge\cdots\ge q_k$, and $q_{k+1}\ge\cdots\ge q_N$, so that \begin{equation} \ep=\sum_1^k(p_i-q_i)=\sum_{k+1}^N(q_i-p_i). \end{equation}
Let $p_i^*:=q_i$ for $i=2,\dots,k$ and $p_1^*:=q_1+\ep[=\sum_1^k p_i-\sum_2^k q_i\le1]$. Then the vector $(p_1^*,\dots,p_k^*)$ majorizes the vector $(p_1,\dots,p_k)$ and still satisfies the condition $p_i^*\ge q_i$ for $i\le k$. Also, $p\ln p$ is strictly convex in $p$, and so, $\sum_1^k p_i\ln p_i$ is strictly Schur convex in $(p_1,\dots,p_k)$. So, wlog $(p_1,\dots,p_k)=(p_1^*,\dots,p_k^*)$.
The range $k+1,\dots,N$ of the indices is considered somewhat similarly to the just considered range $1,\dots,k$. There is an integer $m$ between $k+1$ and $N$ such that $q_{m+1}+\dots+q_N<\vp\le q_m+\dots+q_N$. Let now $p_i^*:=q_i$ for $i=k+1,\dots,m-1$, $p_m^*:=q_m+\dots+q_N-\ep[\in[0,q_m)]$, and $p_i^*:=0$ for $i=m+1,\dots,N$. Then the vector $(p_{k+1}^*,\dots,p_N^*)$ majorizes the vector $(p_{k+1},\dots,p_N)$ and satisfies the condition $p_i^*\ge q_i$ for $i>k$. So, wlog $(p_{k+1},\dots,p_N)=(p_{k+1}^*,\dots,p_N^*)$.
Thus, wlog
\begin{gather}
p_1=q_1+\ep,\quad p_i=q_i\ \forall i=2,\dots,m-1,\\
p_m=q-\ep,\quad p_i=0\ \forall i=m+1,\dots,N,
\end{gather}
where
$$q:=q_m+\dots+q_N.$$
Recall that $p_m=p_m^*\in[0,q_m)$. Let us show that actually $p_m=0$. Indeed, otherwise replace $p_1,q_1,p_m,q_m$ respectively by $p_1+t,q_1+t,p_m-t,q_m-t$ for small enough $t>0$; then all the conditions on $P,Q$ will hold. The derivative of the difference $\De$ in $t$ at $t=0$ is $\ln(\frac{p_1}{q_1}\,\frac{q_m}{p_m})>0$, since $p_1>q_1$ and $q_m>p_m$. This contradicts the condition that $(P,Q)$ is a point of maximum of $\De$. Therefore, indeed $p_m=0$ and hence $q=\ep$. Also, $(q_1+\ep)\ln (q_1+\ep)-q_1\ln q_1$ is increasing in $q_1$; $\sum_m^N q_i\ln q_i$ is Schur convex in the $q_i$'s; and $m\ge k+1\ge2$. So,
\begin{align}
\De&=(q_1+\ep)\ln (q_1+\ep)-q_1\ln q_1-\sum_m^N q_i\ln q_i \\
&\le 1\ln1-(1-\ep)\ln(1-\ep)-\ep\ln\frac \ep{N-m+1} \\
&\le (1-\ep)\ln\frac1{1-\ep}+\ep\ln\frac{N-1}\ep=H(\ep)+\ep\ln(N-1),
\end{align}
which is the desired bound on the difference $\De$.
The exactness of this bound follows from the above reasoning, or from the comment made earlier.