How small can a subsample in bagging be before performance degrades severely? If I want to perform bagging, would subsamples with sizes of 0.1% of the actual data be appropriate?
The reason I want to do so is because my actual data set is very large in the tens of millions.
 A: This depends entirely on the data. It's impossible to give a general answer. The optimal subsample size can't be expressed in terms of $x\%$ of the full data set. What determines the size of a real data set anyway? It's in no way optimal.
To give you some examples, I've had surprisingly good results with bagging on tiny subsamples in text mining (e.g. 40 data points in $~20,000$ dimensions, ~$60\%$ base model accuracy, over $90\%$ ensemble accuracy), but for other data sets you typically need more. There is no rule of thumb, definitely not in the form of "$x\%$ of the full data set".
The simplest approach is to try: e.g. use a couple of small subsamples and bag them, if the ensemble accuracy is much higher than the base models, it's working; if not, use larger subsamples.
Note that using larger subsamples is not guaranteed to improve your results. In bagging you make a tradeoff between base model accuracy and the gain you get through bagging. If you have unstable base models (typically trained on smaller subsamples with lower accuracy), the aggregation may improve the ensemble greatly. When your base models become more stable (typically trained on larger subsamples with higher accuracy), the improvement through aggregation diminishes.
