Но если товар в разных категориях?
Физически картинка расположена в одном каталоге, а категория - сущность виртуальная и непостоянная. Связи "товар-категория" и "товар-путь к картинке" - это записи в базе. Как видно категория и физ расположение никак непосредственно не связаны, а только через товар. Который тоже является просто набором данным в БД.
Есть ощущение, что решение уже придумано
Например в ВП придумано решение раскидывать по датам (год/месяц). Но можно и по др критериям. Для ИМ решение с названием каталогов именами категорий вполне приемлемое.