Thank you for finding this bug... Not sure yet how we will address this in the product, but we'll definitely pick this up in a future release.
The Startup folder is its own separate entity w.r.t. folder redirection (even though it's a sub folder of the programs menu). When it comes to UEM's shortcut creation, any sub folder you entered in the Programs folder text field will just be appended to the effective location of the programs menu folder.
If the programs menu is redirected, we'll create your startup shortcut in <redirectedlocation>\Programs\Startup. But unless you also redirected your Startup folder (using GPO, as UEM does not support that) to that particular folder, Windows will look in the original %APPDATA%\Microsoft\Windows\Start Menu\Programs\Startup location...
For now, my suggestion would be to add a value under HKCU\Software\Microsoft\Windows\CurrentVersion\RunOnce.
Thanks again, and apologies for the issue.