If you converge, you would expect the steps to get small. Ideally, a step $\delta x_k$ in an optimization algorithm would go from the current iterate $x_k$ to the exact solution $x^\ast$, so $\|\delta x_k\| \approx \|x_k-x^\ast\|$ which is, as you approach the solution, going to be small.
Now you say that $\delta x_k$ is getting small even though the gradient is still large. That, of course, depends on how you define "large". Is $10^3$ small or large? By itself, there is no way to say this. It depends on the units of the thing, as well as on what you compare with. Compared with the typical size of objects we have around us, $10^3$ light years is clearly large. $10^3$ nanometers is pretty small, however. But if you're a cosmologist, then $10^3$ light years is small. And if you're looking at atomic distances, then $10^3$ nanometers is large. In other words, you need to investigate what exactly it means for the gradient to be large in your case, and whether a number that is, for example, not on the order of $10^{-7}$ but rather $10^7$ really means that you're still far from the solution.
In the context of optimization problems, you need to ask
"what is small?" when you look at the gradient. One way to approach this is to ask "what is a typical size for the gradient?". To give an example, let us say that you have a spring-mass system for which you'd like to find the minimum energy position. Let's assume that the springs are all around 10cm long, then a typical displacement of springs might be $\Delta x=1cm$. Choose two positions for the bodies and connecting springs that are approximately $\Delta x$ apart and evaluate the energies for these two positions to get a corresponding "typical energy difference" $\Delta E$. Then a "typical size of the gradient" would be $\Delta E/\Delta x$. If your optimization algorithm has produced a position for which the gradient is $\|g_k\| \le 10^{-3} \left|\Delta E/\Delta x \right|$, then you can say that you're converged.