Usually for changing list items in ItemAdding event receiver you should use AfterProperties. But in this particular situation, I've just tried to change the "Title" property in the ItemAdding event receiver, and it doesn't affect anything, silently swallowing any value without any error.
So I assume, if you don't have time for deep investigations, you might prefer to use something more tricky, for example, replace
New Folder button with your own one and capture the execution flow from there.
Assuming you're using SP2010, to replace the New Folder page, you can use custom action approach.
Here is the sample code:
<CustomAction Id="ReplaceNewFolderInDocumentLibraries" Location="CommandUI.Ribbon">
Image16by16="/_layouts/$Resources:core,Language;/images/formatmap16x16.png" Image16by16Top="-16" Image16by16Left="-248"
Image32by32="/_layouts/$Resources:core,Language;/images/formatmap32x32.png" Image32by32Top="-448" Image32by32Left="-320"
In this example, the MyNewFolderForm.aspx page with corresponding markup and code for creating a folder must be deployed by using SharePoint Mapped "Layouts" Folder.
To precise the scope of the custom action, you can either use your own document library definition and point the custom action to it by using
RegistrationId="..." attributes, or use code approach, namely SPList.UserCustomActions collection, to add the custom action to the particular document library instance (regardless of it's content type).
P.S. When dealing with Ribbon customizations, don't forget to refresh the browser cache, since some browsers, especially Internet Explorer, tend to cache SharePoint Ribbon. For IE:
F12 => Cache => Always refresh cache.