Apparently, both titles are produced by Shaft. The Madoka Magica Rebellion movies have short into animation that uses Monogatari characters to ask the viewers to behave in the cinema theaters. I'm interested if there are any other notable connections between the two.
There aren't any substantive connections between the two series, in terms of content.
From a production perspective, though, there is a lot of overlap between them. First, as you noted, they're both produced by Shaft, which means they share a lot of staff, most notable among them director SHINBO Akiyuki, whose directorial flourishes are easily seen in both series. IWAKAMI Atsuhiro is also the producer for both of them, though I'm not sure how much influence he has relative to Shinbo.
The short intro animations you mentioned are primarily amusing because the voice casts of the two series have a lot of people in common:
- SAITOU Chiwa, who voices both AKEMI Homura and SENJOUGAHARA Hitagi
- KITAMURA Eri, who voices both MIKI Sayaka and ARARAGI Karen
- EMIRI Katou, who voices both HACHIKUJI Mayoi and Kyuubey
- MIZUHASHI Kaori, who voices both TOMOE Mami and OSHINO Ougi
Hence, the four different intro animations, each of which features one of these four voice actors.
Generally speaking, Shaft does tend to hire a lot of the same voice actors for their shows, as you can see in this chart. Especially Saitou Chiwa - she's all over the place in Shaft productions.
Oh, one more interesting connection between the two series - Bakemonogatari and Madoka are the first- and second-top-selling late-night anime of all time in terms of discs sold.1 Shaft is clearly doing something right.