Several hours later I succeeded. The lmic library can be used on the Arduino Mega 2560, but I probably had the pin mapping/wiring wrong. Below you find the details of my setup.
Pin mapping:
// Pin mapping
const lmic_pinmap lmic_pins = {
.nss = 10,
.rxtx = LMIC_UNUSED_PIN,
.rst = LMIC_UNUSED_PIN,
.dio = {4, 5, 7},
};