I don't know the exact history (this would've been taking place in early 2011) but I imagine it could've gone either way and someone eventually had to make a decision. Generally speaking, Windows.ApplicationModel has package information along with a bunch of APIs that deal with app-to-app communication, contracts, activation, suspend/resume, and background tasks. Windows.Storage, on the other hand, has everything to do with the file system.
Because appdata folders are probably more closely aligned with the file system than with the "app model" stuff, I can see why Windows.Storage was the landing place. After all, that's where you find all the other file I/O APIs, and I can imagine that if the ApplicationData APIs were in Windows.ApplicationModel, we'd be having the same question about why they weren't in Windows.Storage. 🙂
I would guess that there was probably an argument for putting the package information classes into Windows.Management.Deployment, which is probably it's most natural home. However, the rest of the APIs there are desktop-only and not accessible to Store apps, so it made some sense to put the Package class elsewhere. I expect this decision was probably made well after the decision to put ApplicationData into Windows.Storage.
It's also worth noting that the appdata folders are not technically part of the package, so it's really the installedLocation property that's the aberration. The rest of the Package and PackageId properties come from the Store and describes the package characteristics more than runtime state. Thus installedLocation just so happens to be the link between all the package info and the file system.
In the end, I think the structure that we have actually makes the most sense, because when you start talking about appdata you automatically end up in Windows.Storage.
Knowing the guys in API naming team that bandied all this kind of stuff about (guys like Harry Pierson, Jason Olson, and Brent Rector–and now I can add Howard Kapustein as well), I expect that they discussed all these pros and cons before making a decision. Howard describes it as "sausage making" if you want a great visual image!