Actually, I've always found the idea of alchemy as a magic skill a little strange too, after all, you're not actually casting any spells, nor are you really doing anything overtly supernatural. You're just mixing two or more ingredients to get a potion with a desired effect. I suppose you could argue that the effects themselves are magical in nature, because no matter what combination of herbs you use in real life, you probably won't get a mixture that lets you breathe underwater or glow in the dark. But practicing alchemy in itself doesn't seem to require specifically being skilled in magic. The way I see it, it would just require knowing what ingredients have what effect and how to mix them to get the best results, but you don't need actual magic to use it. And if you look at it from another perspective, there's some logic to making alchemy a stealth skill since it includes poison making, and I'm assuming that's still in the game, and traditionally, the use of poisons is associated with assassins, who are generally stealth characters. Alone, I wouldn't say it justifies alchemy being a stealth skill, but together with other factors Bethesda no doubt considered, I think it supports the choice. Of course, that sort of thing doesn't matter that much anyway, once the class system is removed.
But in any case, this is an issue of game mechanics, really, Bethesda wanted to ensure that each category had six skills, so they put alchemy into stealth, being as magic already had five magic schools and enchanting, or would you say enchanting somehow fits stealth better? If one skill that used to be a magic skill needs to go into stealth, than alchemy is really the only option where it can in any way be argued that it's appropriate.