In my case, Paralems and Pit Lems were done pretty quickly, but I didn't have any external testers for them. Lemmicks a little longer (still no testers).
Lemmings World Tour was about one year in the making, and I still tested it "in the field".
For Lemmings Open Air, I uploaded smaller demo versions during development, which served to "build up some hype". That way I also found my testers, which made this pack much more backroute-proof out of the gate when it was officially released. LOA took about 2 years to make.
My currently in-development packs have been on halt for a long time now (Lemmings: Hall of Fame and Lemmings, Drugs, and Rock 'n Roll). I've made 2-3 more levels for Hall of Fame recently, and I've been working on the music, too. Thought some tracks are much easier to record than others (the L2 Space and L2 Circus soundtracks have drastic changes in rhythm and tempo in them, and especially the Space track has a more complex melody that's hard to figure out just by ear).
I keep getting ideas for other levels, too, but those don't fit inside the "music" theme.
Lemmings: Hall of Fame will definitely be the first of these packs to be completed, though. I just can't say when yet.

So as you can see, the time span to make any given pack varies a lot for me, too.

Though taking more time with one usually seems to increase its quality. Judging by kaywhyn's feedback to the Hall of Fame demo levels so far, that pack might end up being even more difficult than Lemmings Open Air. Which would be nice, given that a) this incentivises people to play the music packs in order (Lemmings World Tour first, then Lemmings Open Air, then Hall of Fame). And b) it's just nice to know if one is capable of creating such a hard pack.
I still hold the assumption that, in order to create something really heard, I'd first have to be able to beat NepsterLems or Lemmings United first (completing SEB Lems would be nice to start with). But then again, we've already established that creating a hard pack seems to be much easier than playing one. ^^