Yes, simulation time is mainly related to meshing.
If every mesh element is not a perfect square (but is a rectangle, triangle, etc.) the simulation time is increased proportionally.
For example in the attached picture the same patch antenna have different meshing shapes. Left patch has only perfect squares, and the right one has square and rectangle shapes. May say is not a big deal, but simulation time for the right patch is almost two times longer than the left one. If the meshing is totally off (e.g. made mainly from triangles and tetrahedral), the simulation time is very long and sometime also is possiblity the simulation to not converge.
I think predicting with accuracy simulation time for very complex structures is very hard. Maybe now EM software become smarter, but years ago was happen many times that the EM simulator to say "time left 1 minute" and I had to wait another hour.