Did the painting mechanic feel innovative or did it quickly become boring?Neither of those. Its a fairly simplistic system which doesn't allow for too much creativity, its more just to look pretty. I imagine if the game was more than 6 hours long it may start to get boring, but they way the game gradually feeds you new things to paint while you're playing through means you shouldn't get bored.
What it does great is the stuff with the genies, how they interact with your paintings and each other. I wouldn't call that innovative either, but its a really fun system, and often extremely charming.