We need to add new folders and files to existing release.
We know that adding new files is possible through patch [msp].
[For process related reasons they do not want to go minor upgrade]
But is it possible to add new folders also via msp?
Sure. You can add components to a feature during a patch and that component can have a CreateFolder element.