Hi Will,
Thanks for contacting us, let me answer you point by point.
Does it work with a CDN like MaxCDN
Yes absolutely, as the plugin does not change the image location, your CDN will keep working as usual
Does it impact performance at all? Especially if I start creating lots of folders?
Like all WordPress plugin there's an impact but it's not one of those plugin which require a lot of resources even with thousands of folders. Folder are based on a WordPress custom taxonomy, so it's very light. I don't think you'll see a difference. Plus, we're testing all our plugins with P3 profiler and other tools to minor as much as possible the performance impact.
Does it impact SEO?
Not at all, images remains at the same place, no changes on path, no broken links. Personal note: if you worry about image and SEO, give a try on our free plugin WP Meta SEO.
Cheers,