No, not reinstall. You can clear the cache by going to the settings menu –> app settings (on my S7 it’s called “Application Manager”, may be a bit different on your phone). There, scroll down until you find Magic Dosbox in the list. Tap it once, and in the next menu, tap “Storage”, then “Clear Cache”. That’s it for Touchwiz Marshmallow, at least.

I see you’re still on Lollipop. It’s possible that the “Clear Cache” button will show up immediately when you tap on Magic Dosbox in the App Manager.

Do the same for your launcher, just to make sure.

If you can’t find the option anywhere, look for “clear cache” on Google Play, there are plenty of apps that can do the job.

Well I tried clearing the cache of both Magic DosBox and my launcher and then restarted; didn’t help

All the shortcuts I create keep reverting to “Magic DosBox” upon restart

Maybe it never work correctly…you wrote you didn’t restart device for a long time, so maybe you only didn’t notice that.

Sure, that’s possible.

Can’t you somehow detect name of the launcher?

I think I found it – Launcher3 it’s called.
From what I can gather it comes pre-installed on quite a lot of phones – especially Chinese-brand ones.
Found what looks like its source here: https://android.googlesource.com/platform/packages/apps/Launcher3/
Someone says that the Google Now Launcher is based off of it.

What’s interesting though is that I have another app – Xash3d FWGS – that can also create shortcuts; and those shortcuts keep their names when I restart the phone. So, we know it’s possible to have permanent-name shortcuts for this launcher, at least.

Can you try another launcher for a test?

Sure, that sounds like a reasonable course of action to narrow down the culprit in the matter. Maybe tonight or tommorow, when I have the time.