I have the exact same problem and use Notepad++ to do a "Find and Replace In Files" every time I need to update the playlists... such a pain!
M3U is a pretty dumb format for this. You either end up with:
1) Static lists e.g. C:\music\mysong.mp3
- The playlist file can be anywhere
- Can't be copied to external device due to drive letter difference
- Doesn't work if on mobile phone or similar
- Can't move music
2) Relative lists e.g. \billy joel\mysong.mp3
- Can be copied to any other device/external
- Whole music library can be moved
- Sometimes gets complicated when you get to ..\..\..\billy joel\mysong.mp3
- Playlist must remain in same folder hierarchy as music
In an ideal world, MusicBee would automatically update the M3U file for you whenever you moved it, automatically detecting what it should replace the directory and drive letter paths with.
However in the meantime Notepad++ does the job, even if it's kinda clunky! :-)