Google Music Gapless Playback Works on my Galaxy Nexus but not my HTC One?
This is a symptom of the phone's hardware, not Android, Google Play or your uploaded/cached music. I have the same problem with a 1st gen. Moto G (LTE/4G) with about 1s gap between songs, despite 4 cores and no other noticeable performance problems, but the same music works perfectly in Google Play on a laptop.

I've read many reports where the same version of Android provides gap-less for some users, but not others. This means it's either a hardware limitation or the file I/O processes are single threaded and take time to drop the current track before loading up the next one.

My experience is that using a faster phone fixes this problem.