Cannot implicitly convert List<T> to Collection<T>

Why not just do the following:

Collection<string> collection = new Collection<string>(theList);

as Collection(IList input) takes a List as part of construction.

List<T> doesn't derive from Collection<T> - it does, however, implement ICollection<T>. That would be a better choice of return type.

As for the new List<int>(some collection<int>) question - it partly depends on what the collection is. If it implements ICollection<T> (at execution time) then the constructor can use its Count property to create the list with the right initial capacity before iterating through it and adding each item. If it doesn't implement ICollection<T> then it's just equivalent to:

List<int> list = new List<int>();
foreach (int x in otherCollection)
{
    list.Add(x);
}

Still nice to have in a convenient constructor, but not hugely efficient - it can't be, really.

I don't believe the constructor does anything cunning for arrays, which it potentially could - using Array.Copy or whatever to just copy the lot in one go rather than iterating though. (Likewise if it were another List<T> it could get at the backing array and copy that directly.)

List<T> doesn't inherit from Collection<T>. Plain and simple. Unless List<T> provides an operator to implicitly convert to/from Collection<T>, you can't do it. I would actually suggest returning List<T> if you can, as I believe the rules go something like this:

Accept as a parameter the least constrictive interface possible. Return as a return parameter the most constrictive type possible.