Are mules subject to the same encumbrance rules as PCs, leading them to only be able to carry 40lbs of gear? Or is there a more realistic number someplace I'm missing?
The encumbrance rules are intended for PCs, although a rule of thumb recommended by the Savage Worlds Core Rules Brand Manager is to double the carrying capacity for each point of Size. Thus a mule with Strength d8 and Size +2 would be able to carry 160lb without penalty, or 640lb with a -3 penalty.
However, from the two sources provided by @Phil, it seems a mule can normally carry around 20–30% of its body weight, so if you're aiming for a more realistic figure you could try a rule like "four-legged creatures double their carrying capacity".