I don't think it was the Bard's Tale. From the games I've seen, it either looks way, way older than what I'm thinking or a little too new. It probably wasn't at all any older than doom, since it does seem to do the whole "Fake 3D" procedural texture drawing/chunk loading thing that Doom did,and it had multiple floors and ladders and shit that you sure as hell couldn't do with the pre-doom Raycaster 3D.
The textures were about the same resolution too, but low-budget and a bit shit. The place where you talk to the King/leader of the city featured a live-action dude in front of some gifs of a bare bones, 3D-animated castle interior. (I could be wrong about the background being some sort of 3d model, but that's how it looked to me.)
I'm still pretty sold on it being one of the M&Ms, or at least something tied to Dungeons and Dragons, because there seemed to be more than a few other TSR/Wizards-related properties besides just the friendly mindflayer. The dark elves you could choose to make were explicitly referred to as Drow, (Not sure if they own the name, but that is a D&D trope.) you could choose your characters' starting class levels (up to 30, I think?) and a few other options that seemed really geared toward porting existing tabletop characters into the game, with the game itself sort of acting as a module.
There was even a segment right out of the old D&D books if you chose to roll up a new character (With actual randomly generated stats) where it says something along the lines of "Don't worry if you think your character is too shitty for this adventure, because you can always reroll unless you feel like that's cheating!" The way they used to do before Tabletop RPGs decided to give you a set amount of points to spend on your attributes.