The folder solution would be recommended ONLY if the permission on these images are going to be very granular. Normally libraries that contain documents such as Policy & Procedures would use folder potentially but in your case I would say you wouldn't.
With that said the solution of creating 2 choice columns for "Year" and "Month" is going to be a great solution. Once all your documents are tagged with a year and month you can then "group" the documents by year and month to ensure your users can navigate through the images similar to a folder structure :) As for performance concerns, your image library should not slow down if your view item limit isn't greater than 50 per page. If so you may have a separate issue in performance needs.
Recap - Steps to your solution:
- Create 2 Choice Columns (Year, Month)
- Apply the correct metadata to all content
- (Optional) Group the files to ensure user can easily navigate images
- Ensure your item limit is >= 50