Huh, removing the angle brackets resilved the issue:
This works:
#include "/home/maxg/Documents/PlatformIO/Projects/MavLink_Test1/.pio/libdeps/megaatmega2560/MAVLink v2 C library/ardupilotmega/mavlink.h"
So does this:
#include "../.pio/libdeps/megaatmega2560/MAVLink v2 C library/ardupilotmega/mavlink.h"