Pros and cons of both methods:
- accuracy (thanks to its better approximation series it yields a 4th order precission)
- artificial/inherently induced damping (a bit like implicit methods do it) adds stability (whereas a simple Euler step doesn't - it does the opposite actually, introducing ghost energy that builds up and could plunge the system into chaos)
- computation expense: while not that demanding in comparison to implicit methods or hybrid IMEX methods, RK4 is 4 times more expensive than the explicit Euler since it requires that many more function evaluations. This shows when aiming for the bleeding edge of optimization.
- still unstable: depending on the types of forces involved, RK4 can be just as unstable as Euler. On average, RK4 is a bit more stable and tends to draw this benefit from its endowed damping "skills".
- Non-symplectic: numerical damping comes with a cost - you cannot simulate systems where energy/volume/etc. loss shouldn't apply a visible effect over time (e.g. Molecular Dynamics, Potential Field derived forces, variational problems)
- once or two times the complexity of an Euler step (depending on your Verlet flavour: position or velocity).
- symplectic: conserves internal energy
- second order accuracy: many games do not require high precision floating point results, and second order is more than pleasing for the eye in a game scenario (plus: it was used in a non-gaming scenario simulation when it was "discovered", so it's not that bad)
- stable, but still: probably the best explicit method in terms of stability. It tends to win the edge when hard constraints are added to the system, thus allowing for less head-aches when implementing projected constraints in position based dynamics engines. It sets off to infinity if the system is perturbed with large external forces and no damping/friction is added. Even so, there are certain numerically imposed limits to how large the internal (spring) forces can be, but they're higher on average than what RK4 can do
- lower accuracy: not useful if you want high precission estimations
- requires, on average, smaller time-steps than RK4 for some simulations (RK4 benefits from both its accuracy and internal damping)
Using one over the other depends on the scenario. If stiffness and large external forces and virtual energies are a problem, then consider other methods having the "implicit" word in their description/title.
Note some authors/books use the term semi-implicit Euler for an actual explicit Euler integrator called the symplectic Euler method (or Euler Cromer) from which Verlet is actually derived. Verlet is also called by some people the "leapfrog method". Velocity Verlet and the midpoint method are fairly similar since an estimation at a time step of
t + 0.5*dt is required for a predictor-corrector-like step. IMEX methods (implicit-explicit) are also used to name two similar but not identical approaches: separate the computations into stiff and non-stiff parts and use different integrators on them (the explicit for non-stiff, implicit for stiff) OR solve for the velocity with an implicit update step and update the position in an explicit manner (this is a hybrid semi-implicit method falling on the IMEX class of methods because the stiff parts affect the acceleration computation the most). Implicit methods are more cumbersome and require solving a system of simultaneous non-linear equations for the entire configuration. Implicit methods are used for deformable bodies and usually aren't used for decoupled rigid bodies.
As stated in one of the comments, if you can, do not use Euler. Use either the midpoint method, the semi-implicit Euler or, at the same expense, the position-Verlet. All of them have slightly higher accuracy and sensibly more stability than the explicit Euler integrator.
Recommended mini-comparison reading: