Q:

How do you convert a SortedList into a SortedList<>

Due to the existing framework I am using, a method call is returning a SortedList object.   Because I wrote the other side of this call I know that it is in fact a SortedList.   While I can continue to work with the SortedList, using the generic would convey my meaning better.   So, how do you change the non-generic SortedList into an appropriately typed generic SortedList? 
The background on this is that the call is a remote procedure call using the SoapFormatter.   The SoapFormatter does not implement generics (Thank you, Microsoft).  I cannot change the formatter since some non-.Net programs also use other method calls against the service. 
I would like my proxy call to look like the following:
public SortedList<string, long> GetList(string parameter)
{
    return _service. GetList(parameter);
}

Where the interface for the GetList call is as follows due to the SoapFormatter requirements:
public SortedList GetList(string parameter);

A:

You can't directly convert, as a SortedList is not actually a SortedList<T>, even if it only contains elements of type T.
In order to turn this into your appropriate type, you'd need to create a SortedList<T> and add all of the elements into it. 

A:

A conversion function for your usage:
static SortedList<TKey,TValue> StronglyType<TKey,TValue>(SortedList list) {
    var retval = new SortedList<TKey,TValue>(list. Count);
    for(int i=0; i<list. Count; i++) 
        retval. Add((TKey)list. GetKey(i), (TValue)list. GetByIndex(i));
    return retval;
}

The equivalent foreach(DictionaryEntry entry in list) approach is slightly slower due to the implicit cast to unbox the DictionaryEntry (you always need the casts to TKey/TValue). 
Ballpark performance overhead: On my years old machine here, this function takes 100ms to convert a 1000 lists with 1000 entries each. 