I'd use the find command piped to mv and play with some empty test folders first. I'm not familiar with Nemo, though I've used it for a short while. I've never tried the bulk renaming features if they exist.

Depending in how much variation you have in the preceding underscores, REGEX may be useful, but if its just a lot of single underscores you can easily trim them with a single version of the script.

Edit: corrected second command typo. I think there's a rename command I haven't used in ages that may have args to help here too, but I'm away from the PC

Hey, I wrote a script for you since this was a really simple operation. I have 2 versions depending on what you want them to do.

I recommend that you make a test folder with a bunch of test directories and subdirectories to make sure this works as expected on your machine.

The first will only rename folders with a depth of 1 (meaning it won't rename subdirectories). This is for if you want to control which specific directories you run this on.

Non-subdirectory version

#!/bin/bash

find . -maxdepth 1 -type d -name "_*" | while read FOLDER; do
    newfolder="$(echo ${FOLDER} | sed -e 's/^\.\/___/a/' | sed -e 's/^\.\/__/b/' | sed -e 's/^\.\/_/c/')" ;
    mv "${FOLDER}" "${newfolder}" ;
done

The second renames all folders including subdirectories (it goes 1 layer deeper at a time). So if you want to just run this from your home directory (or wherever the drive you want to run it on is mounted), you can run it once and be done with it. It only goes 100 folders deep, but you can modify that by changing the {2..100} to another range, like {2..500} for 500 folders deep. Running more layers deep increases runtime, so I assumed you wouldn't have more than 100 layers of folders, but if you do you can adjust it.

Subdirectory version

#!/bin/bash

find . -maxdepth 1 -type d -name "_*" | while read FOLDER; do
    newfolder="$(echo ${FOLDER} | sed -e 's/^\.\/___/a/' | sed -e 's/^\.\/__/b/' | sed -e 's/^\.\/_/c/')" ;
    mv "${FOLDER}" "${newfolder}" ;
done

for i in {2..100};
do
    find . -mindepth $i -maxdepth $i -type d -name "_*" | while read FOLDER; do
        newfolder="$(echo ${FOLDER} | sed -e 's/\/___/\/a/' | sed -e 's/\/__/\/b/' | sed -e 's/\/_/\/c/')" ;
        mv "${FOLDER}" "${newfolder}" ;
    done
done

I assume that you at most have 3 underscores preceding a folder name. If that is not the case, you can modify the script as following.

If you have more, copy one | sed 's/.../' part for each find section up to the next | symbol (there is only 1 find section for the no subdirectory version and 2 find sections for the subdirectory version) and paste it before or after the others. If you are using the subdirectory version, make sure you copy the corresponding version of the sed command because they differ (the first one containes "^." that the second one doesn't)! On your new pasted copy, add an underscore to the part of the text you pasted that has underscores. Then for each of the other sed blocks, change the letter they are replaced with to match.

Here is an example with 4 max underscores on the subdirectory script:

#!/bin/bash

find . -maxdepth 1 -type d -name "_*" | while read FOLDER; do
    newfolder="$(echo ${FOLDER} | sed -e 's/^\.\/____/a/' | sed -e 's/^\.\/___/b/' | sed -e 's/^\.\/__/c/' | sed -e 's/^\.\/_/d/')" ;
    mv "${FOLDER}" "${newfolder}" ;
done

for i in {2..100};
do
    find . -mindepth $i -maxdepth $i -type d -name "_*" | while read FOLDER; do
        newfolder="$(echo ${FOLDER} | sed -e 's/\/____/\/a/' | sed -e 's/\/___/\/b/' | sed -e 's/\/__/\/c/' | sed -e 's/\/_/\/d/')" ;
        mv "${FOLDER}" "${newfolder}" ;
    done
done

If you have fewer than 3 max underscores, you just delete the relevant sed parts and update the letters.

You can also let me know how you want if modified and I can do it for you if you'd like.

Using the subdirectory version

If you want to use the one that works on subdirectories, create a text file renamesubdirectories.sh in the folder you want it to start from, and paste in the subdirectory script into that file with whatever text editor you prefer. You can then modify the script if necessary.

I'm going to try to give GUI instructions, but I haven't used Nemo in a long time, so I've also provided terminal instructions in case those don't work.

Nemo

Navigate to the folder you want to start from in Nemo. Copy or move the renamesubdirectories.sh file into this folder (or create the file here if you haven't done so already, and paste in the subdirectory script, modifying if necessary). Right click on the file and open its properties/permissions (maybe details? Can't remember exactly what the option is called). Find the setting to adjust permissions of the file, and allow it to be executed as a program/mark it executable, whatever adding the executable permission is called in Nemo. Now you can exit the permissions/properties/details window, and right click the file and run. After a few seconds, refresh (F5 usually). You should now be done and can delete the file.

Terminal

Navigate to the folder you want to start from, and right click > Open in terminal (I believe Nemo has that option, but it's been awhile; let me know if not, and I can explain now to navigate there from terminal). Now make the file executable with chmod +x renameunderscores.sh. Run it with ./renameunderscores.sh. Once the next line prints (with your username, hostname, and directory), the command is done and you can exit the terminal and delete the file.

Using the non-subdirectory version

This will require you to either move the script every time you want to run it, or installing it locally and using the terminal (which is easier). I will explain the terminal version only for this, as moving the script every time you want to use it is very tedious.

Again, create the renamesubdirectories.sh file using the text editor of your choice, and modify as necessary. Then create a folder called bin in your home folder (this should automatically be in your path) and copy or move the renamesubdirectories.sh file into that folder. Then (in the bin folder) right click and open in terminal in Nemo, or just open a terminal from applications and navigate to the folder with cd ~/bin. Now make the file executable with chmod +x renameunderscores.sh.

You should now be able to navigate to any folder you want, then right click open in terminal, and run the command renameunderscores.sh. Once you are finished, you can delete the bin folder.