The least you can do is given by Shannon-Nyquist theorem: to be able to read a signal, you shall sample at least twice its frequency. Here, you can sample at 20MS/s (Mega sample per second). Nevertheless, 2 points for one period is very few, and introduce much jitter on the rebuilt signal.
Your logic analyzer won't share your signal clock. This is a common case in transmission, and I would advise you to do the same as most UART/SPI/I2C/... interface: take 3 points per state. This allow to filter EMC noise using a majority filter, and, when analyzing, allows to see significant skew between your signals. Please note that the clock of a 10MHz SPI bus goes both high and low every 100ns period, so you need to sample at 6 times your SPI frequency (60MS/s).
60MS/s is common for logical analyzers, and this will allow you to detect excessive skew (between your data and your clock) for most protocols (including SPI). Nonetheless, with a non-symmetric clock (with tHIGH != tLOW), you'll need to sample fast enough to sample the shortest part of the clock. If you clock is HIGH for 1µs and LOW for 9µs, you've got a 100kHz signal, but need 3MS/s.
This answer only considers the signal you want to analyze. For EMC issues, we usually use analog scopes with a sampling frequency 10 times higher than the highest frequency in the system, but it's a bit expensive, and off-topic, considering that the question is to decode an SPI bus.