Little disclaimer: I posted this on reddit too!
I love melodic music and often prefer instrumental bands. So far I only know Demetori. (Don't judge it by the anime pictures if you're not into that.) They make covers of music from a game series, so it's bound to be melodic. And they're really good! Here's another great one from them. They make some lighter stuff, too.
Another example: The Black Mages. Again, they make video game covers. But Nobuo Uematsu is a member of the band, so they're awesome too!
One more example is Akira Yamaoka, but his style is more like rock.
Are there any melodic but instrumental bands out there? Progressive style is always a bonus.