tldr; If $\Delta v>c$, its a reference frame issue. Use rapidity to calculate $\Delta v$ instead. If $v_e > c$, then there is no solution for the specified conditions, because the exhaust velocity requires more energy input than there is mass-energy in the fuel.

$\rule{10cm}{0.4pt}$

There are 2 parts to this question that can be addressed. When solving the rocket equation, there are 2 velocities that can be solved for (given the other variables) and either could exceed the speed of light if the right numbers are used.

(1) What if $\Delta v > c$?

(2) What if $v_e > c$?

The first question is answered by considering reference frames. A $\Delta v$ larger than the speed of light does not mean the rocket's velocity relative to the initial inertial frame is greater than $c$. Instead, it is the measured $\Delta v$ in the frame of reference of the rocket that is. It is similar to the scenario where you can accelerate at 1g for 2 years, but your velocity is not $2c$, however your observed (integrated) $\Delta v=a\Delta t$ is larger than $c$. There is nothing wrong with this.

The correct way to compute your actual change in velocity is to consider the correct reference frame and integrate the local change in velocity relative to that reference frame. In all reference frames, $$dp_{ex} = dp_{rocket}$$ In the local frame of the rocket, relativistic effects of the rocket's velocity are ignored. So $dp_{rocket} = (m-dm)dv$ and the classical rocket equation results, and $\Delta v$ may be greater than $c$. Instead, if we consider an inertial frame of reference, $$dp_{rocket} = (m-dm)d(\gamma v)$$ The resulting solution to the rocket equation can be easily put in terms of a term called rapidity. The neat property of rapidity is that it adds just like velocities do in Galilean relativity. $$r \equiv \tanh^{-1}\left(\frac{v}{c}\right)$$ $$\Delta r = \frac{v_e}{c}\ln\left(\frac{m_i}{m_f}\right)$$ This allows you to calculated the actual $\Delta v$ relative to the initial inertial frame of reference.

$\rule{10cm}{0.4pt}$

On to the second question: what if $v_e>c$? Returning to first principles, we know that $$dp_{ex} = dp_{rocket}$$ and should the rocket velocity not be relativistic, then $$\gamma_e v_e dm_{ex} = (m-dm_{r})dv_{r}$$ However, there is a hidden nuance with this equation (Thanks to @Litho for catching this). With chemical rockets (low exhaust velocities), the mass of the exhaust leaving the rocket is equal to the change in mass of the rocket according to the principle of conservation of mass. $$dm_{ex} = dm_{r}, \hspace{10pt} \gamma = 1$$ But in relativity, one of the first lessons is that mass is not conserved! Instead, mass-energy is. Therefore if the exhaust is expelled at velocity $v_e$, then this kinetic energy comes from its initial rest mass. Starting from the energy-momentum relation $$E^2 = (mc^2)^2 + (pc)^2$$ and using the definition for an object at rest, $E = m_{rest}c^2$, one can show (algebra) that for a mass $m$ moving at speed $v_e$: $$m_{rest} = \gamma m, \hspace{10pt} \gamma = \frac{1}{\sqrt{1-{\frac{v_e^2}{c^2}}}}$$ $$dm_{rocket} = \gamma dm_{ex}$$ This factor of $\gamma$ cancels with the $\gamma$ in the momentum equation above, and so the solution is actually the classical rocket equation. Therefore, the classical rocket equation holds even for relativistic exhaust velocities.

So what happens when $v_e>c$? You are S.O.L. The energy required to achieve this exhaust velocity is larger than the initial mass-energy of the fuel. There is no solution for $v_e$ for the $\Delta v$ and masses specified.

tldr; If $\Delta v>c$, its a reference frame issue. Use rapidity to calculate $\Delta v$ instead. If $v_e > c$, then there is no solution for the specified conditions, because the exhaust velocity requires more energy input than there is mass-energy in the fuel.

$\rule{10cm}{0.4pt}$

There are 2 parts to this question that can be addressed. When solving the rocket equation, there are 2 velocities that can be solved for (given the other variables) and either could exceed the speed of light if the right numbers are used.

(1) What if $\Delta v > c$?

(2) What if $v_e > c$?

The first question is answered by considering reference frames. A $\Delta v$ larger than the speed of light does not mean the rocket's velocity relative to the initial inertial frame is greater than $c$. Instead, it is the measured $\Delta v$ in the frame of reference of the rocket that is. It is similar to the scenario where you can accelerate at 1g for 2 years, but your velocity is not $2c$, however your observed (integrated) $\Delta v=a\Delta t$ is larger than $c$. Here, $a$ is the local acceleration you would feel onboard the rocket, however the observer from an inertial frame would observe a different acceleration.

The correct way to compute your actual change in velocity is to consider the correct reference frame and integrate the local change in velocity relative to that reference frame. In all reference frames, $$dp_{ex} = dp_{rocket}$$ In the local frame of the rocket, relativistic effects of the rocket's velocity are ignored. So $dp_{rocket} = (m-dm)dv$ and the classical rocket equation results, and $\Delta v$ may be greater than $c$. Instead, if we consider an inertial frame of reference, $$dp_{rocket} = (m-dm)d(\gamma v)$$ The resulting solution to the rocket equation can be easily put in terms of a term called rapidity. The neat property of rapidity is that it adds just like velocities do in Galilean relativity. $$r \equiv \tanh^{-1}\left(\frac{v}{c}\right)$$ $$\Delta r = \frac{v_e}{c}\ln\left(\frac{m_i}{m_f}\right)$$ This allows you to calculated the actual $\Delta v$ relative to the initial inertial frame of reference.

$\rule{10cm}{0.4pt}$

On to the second question: what if $v_e>c$? Returning to first principles, we know that $$dp_{ex} = dp_{rocket}$$ and should the rocket velocity not be relativistic, then $$\gamma_e v_e dm_{ex} = (m-dm_{r})dv_{r}$$ However, there is a hidden nuance with this equation (Thanks to @Litho for catching this). With chemical rockets (low exhaust velocities), the mass of the exhaust leaving the rocket is equal to the change in mass of the rocket according to the principle of conservation of mass. $$dm_{ex} = dm_{r}, \hspace{10pt} \gamma = 1$$ But in relativity, one of the first lessons is that mass is not conserved! Instead, mass-energy is. Therefore if the exhaust is expelled at velocity $v_e$, then this kinetic energy comes from its initial rest mass. Starting from the energy-momentum relation $$E^2 = (mc^2)^2 + (pc)^2$$ and using the definition for an object at rest, $E = m_{rest}c^2$, one can show (algebra) that for a mass $m$ moving at speed $v_e$: $$m_{rest} = \gamma m, \hspace{10pt} \gamma = \frac{1}{\sqrt{1-{\frac{v_e^2}{c^2}}}}$$ $$dm_{rocket} = \gamma dm_{ex}$$ This factor of $\gamma$ cancels with the $\gamma$ in the momentum equation above, and so the solution is actually the classical rocket equation. Therefore, the classical rocket equation holds even for relativistic exhaust velocities.

So what happens when $v_e>c$? You are S.O.L. The energy required to achieve this exhaust velocity is larger than the initial mass-energy of the fuel. There is no solution for $v_e$ for the $\Delta v$ and masses specified.