A quick thing to try. Change the setting to 'use LinuxMCE's directory structure'. Reboot. It will create public\data\videos and public\data\audio folders on your network share. Try moving the media to those 2 folders. And on the linuxmce box, /home/public/data/videos/ (and audio) will contain symlinc's to those folders, which will be mounted in /mnt/device/xxx.
now go into media files sync, under videos, confirm it has the share, and then see if the files are there with the icon indicating they are already in the database and on disk. Then see if they show up in media browser.
One problem when you say not to use linuxmce's directory structure (which means it's root directory is mounted in /home/public/data/other) is that the UpdateMedia daemon which catalogs the media ends up seraching the entire share. If you have zillions of files, this is very slow. But there's no other way since UpdateMedia can't know what directories really have media needing scanning and what doesn't.
So my recommendation is to use LinuxMCE's directory structure whenever your network share has a bunch of stuff besides just media so UpdateMedia isn't wasting tons of time trying to catalog non-media files.