I have calculated an upper bound and modified a calculation of a lower bound for a similar game. I assume the real size is closer to the upper bound.
$$ 7.36 \cdot 10^{27} \leq |SPADES| \leq 3.09 \cdot 10^{72} $$
Upper bound
The State-space complexity of Spades can be computed by counting for each possible starting state (deal), all the possible sequences of actions. While that calculation could be hard, an upper bound is easy to achieve by multiplying the number of initial positions $|S_0|$ by an upper bound on the number of different possible histories $|\bar{H}|$.
$$ |SPADES| = \sum_{s \in S_0} |H_{s}| \leq |S_0| \cdot |\bar{H}| $$
The number of possible starting positions $|S_0|$ is the number of different ways to deal a 52 cards deck into 4 players
$$|S_0| = \frac{52!}{13!^4} \approx 5.3\cdot10^{28}$$
An information set in Spades contains two objects: the player's hand, and the sequence of actions each of the players have made from the start of the round. Before any card is played, each information set (a single hand) can be completed into a full game-state (4 hands) in the following number of ways
$$ |\bar{S}| = \frac{39!}{13!^3} \approx 8.45 \cdot 10^{16} $$
During a round, each player first decide upon a bid, then choose one out of her 13 cards, than choose one out of 12, etc. Thus, the size of the decision tree, which is the number of histories is bounded by
$$|H| \leq {14!}^4 \approx 5.77 \cdot 10^{43}$$
This is an upper bound since some of those histories violates the rules of the game.
Therefore, the number of legal positions in Spades is bounded by
$$ |SPADES| = \sum_{s \in S_0} |H_{s}| \leq |S_0| \cdot |H| \leq \frac{52!}{13!^4} \cdot {14!}^4 \approx 3.09 \cdot 10^{72} $$
Lower bound
In the paper: Understanding the Success of Perfect Information Monte Carlo Sampling in Game Tree Search, Sturtevant et al. describe a loose lower bound for the size of Skat:
Skat is a 3-player card game with 32 cards, from which 10 are dealt
to each player. There are $$ {32 \choose 10} = 364, 512, 240 $$hands each
player can have and
$$ H := {22 \choose10} \cdot {12\choose10} = 42, 678, 636 $$
hands for the other players which is what constitutes an information set at the start of a game. At the beginning of each trick, the trick leader can choose to play any of his remaining cards. Therefore, there are at least
$$ 10!H \approx 1.54 · 10^{14}$$
information sets. But, from an opponents perspective there
are actually 20 or 22 unknown cards that can be lead, so this
is only a loose lower bound on the size of the tree. This
should clearly establish that even when using short decks it
is infeasible to solve even a single game instance of a trick-based
card game.
Using the same logic to produce a loose lower bound on the size of Spades tree produce the following:
$$ H := {39 \choose 13} \cdot {26 \choose 13} = 8.45 \cdot 10^{16} $$
At the start of the round (before bidding has been made) the number of information sets is lower bounded by
$$ 14!H \approx 7.36 \cdot 10^{27}$$
