I really need to find this location as I've got about a 100 saved games and everytime I load up a saved game, I have to scroll all the way down using the arrow keys.
Funnily enough there is a subfolder called SAVEGAME that is empty and I can't seem to find the files on my computer, even after I search.

Hmm, my SaveGame subfolder isn't empty. All my savegames are there. File ending is *.sg - maybe you can search for this filetype on your harddisk.
But you have to take care, that there are two independent SaveGame folders: one under "Dark Prophecy..." and one under "Rise of the Elves". Did you check both?

Not only are BOTH folders empty, but doing a search (I'm using Vista) in the entire hard drive C: only gives me a list of all the scenario files in the Exports folder (which also have an .sg extension).
I even did a search for the exact name of one of my saved game files.

I can confirm that, on XP SP3, the save file are correctly into "Disciples 2 - Dark Prophecy and Gallean's Return\SaveGame" folder

Typically, save folders in Vista (that's what I use, too), will save in one of two different spots.
It MIGHT create a folder for the game in your Documents folder...you can access that directly as one of the options in the top right of your start menu selection. Just go to Documents.
The OTHER option is in your Appdata folder (for this one, you need to have the option turned ON to let you see Hidden Folders when you're searching through My Computer.) Off the Start menu, click Computer (middle of the menu on the right). If you need to activate the ability to see Hidden Folders, Hit Organize at the top left of the Computer screen, and select Folder and Search Options. In THAT submenu, go to the View tab along the top. About 1.3-1/2 of the way down the options list is a selection marked 'Show hidden files and folders'...select that. Now Apply, and close that window.
Okay, NOW in the list to the left on the Computer list, you'll see, from the top, Desktop...under that will be your log on account name...go there. One of the top folders you can go to in there will be called AppData...go in to that.
From here, it's either in Local or Roaming...there will be a folder for GOG, with each game having a sub folder. Your saves SHOULD be somewhere in there. If not, the last thing I can think of us (from inside the Local subfolder), go in to VirtualStore, then ProgramFiles.
Hope one of those works for you!

Awesome! Thanks to your suggestions, I finally found the save game files in the VirtualStore folder. The thing is that even with Advanced Search searcihng the entire C: and D: drive, Vista doesn't seem to include VirtualStore, which was driving me crazy. Thanks a million!

You're welcome, pangyan...glad to be of help! Those same spots are the areas where savegames and stuff like that for almost any game you install will go with Vista, by the way, so you know for the future.

C:\Users\[username]\AppData\Local\VirtualStore\Program Files (x86)\Strategy First\Disciples 2 Expansion\SaveGame
This was on Windows 7 64, the original (disc) edition with some expansions. Has worked fine, btw, under this OS. Son hijacked my discs, however :) and didn't have the elf expansion.