Ну строго говоря, можно костыльно учитывать добавление-удаление :)

Я его декомпилировал Рефлектором в свое время. Насколько я вижу — вроде логарифмический.

internal SortedSet<T>.Node FindRange(T from, T to, bool lowerBoundActive, bool upperBoundActive)
{
  SortedSet<T>.Node node = this.root;
  while (node != null)
  {
    if (lowerBoundActive && this.comparer.Compare(from, node.Item) > 0)
    {
      node = node.Right;
    }
    else
    {
      if (!upperBoundActive || this.comparer.Compare(to, node.Item) >= 0)
        return node;
      node = node.Left;
    }
  }
  return (SortedSet<T>.Node) null;
}

Правда, там еще потом какой-то VersionCheckImpl() делается...

UPD1: В общем, вот весь остальной код.

public virtual SortedSet<T> GetViewBetween(T lowerValue, T upperValue)
{
  if (this.Comparer.Compare(lowerValue, upperValue) > 0)
    throw new ArgumentException("lowerBound is greater than upperBound");
  else
    return (SortedSet<T>) new SortedSet<T>.TreeSubSet(this, lowerValue, upperValue, true, true);
}

public TreeSubSet(SortedSet<T> Underlying, T Min, T Max, bool lowerBoundActive, bool upperBoundActive)
    : base(Underlying.Comparer)
{
    this.underlying = Underlying;
    this.min = Min;
    this.max = Max;
    this.lBoundActive = lowerBoundActive;
    this.uBoundActive = upperBoundActive;
    this.root = this.underlying.FindRange(this.min, this.max, this.lBoundActive, this.uBoundActive);
    this.count = 0;
    this.version = -1;
    this.VersionCheckImpl();
}

private void VersionCheckImpl()
{
    if (this.version == this.underlying.version)
      return;
    this.root = this.underlying.FindRange(this.min, this.max, this.lBoundActive, this.uBoundActive);
    this.version = this.underlying.version;
    this.count = 0;
    base.InOrderTreeWalk((TreeWalkPredicate<T>) (n =>
    {
      SortedSet<T>.TreeSubSet temp_31 = this;
      int temp_34 = temp_31.count + 1;
      temp_31.count = temp_34;
      return true;
    }));
}

UPD2: Судя по тому, что он зачем-то так по-дурацки считает количество вершин в получившемся поддереве — таки линейный... Брр, неужели?

UPD3: Вот этот код работает за 32 секунды. Отвратительно.

var s = new SortedSet<int>();
int n = 100000;
var rand = new Random(13051991);
int sum = 0;
for (int i = 0; i < n; ++i) {
    s.Add(rand.Next());
    if (rand.Next() % 2 == 0) {
        int l = rand.Next(int.MaxValue / 2 - 10);
        int r = l + rand.Next(int.MaxValue / 2 - 10);
        var t = s.GetViewBetween(l, r);
        sum += t.Min;
    }
}
Console.WriteLine(sum);