Base62というのは、ざっくりいうとBase64から記号を省いて、短縮URLなどに使いやすくしたものです。

使用する文字は、'A'～'Z'、'a'～'z'、'0'～'9'の62種類です。

Base64では、64種類の英数字記号に加えて、パディング記号が定義されていますが、Base62にはパディングがありません。したがって、Base62文字列からバイト配列に変換するときは、元のバイト配列の長さがどれだけだったかを外から与える必要があります。（追記）すみません間違いでした。計算すればいいですね（1バイトはBase62だとおよそ1.35文字）。コードを直しました。（さらに追記）とはいっても長い文字列から正しいバイト数を誤差なく計算するのは難しいです……が、2GB (≒2^31バイト)あたりまで誤差なく計算できれば問題ないでしょう。

using System;
using System.Linq;
using System.Numerics;
using System.Text;

class Base62
{
    public static string ToBase62String(byte[] bytes)
    {
        if (bytes == null) throw new ArgumentNullException("bytes");
        if (bytes.Length == 0) return "";
        var charLength = (int)Math.Ceiling((double)bytes.Length * Math.Log(256d, 62d));

        const string characters = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
        var number = ToUnsignedBigInteger(bytes);

        var chars = new char[charLength];
        var base62 = new BigInteger(62);
        for (var i = 0; i < charLength; i++)
        {
            BigInteger mod62;
            number = BigInteger.DivRem(number, base62, out mod62);
            chars[i] = characters[(int)mod62];
        }
        return new string(chars);
    }

    static BigInteger ToUnsignedBigInteger(byte[] bytes)
    {
        var zeroAppended = new byte[bytes.Length + 1];
        bytes.CopyTo(zeroAppended, 0);
        var unsigned = new BigInteger(zeroAppended);
        return unsigned;
    }

    public static byte[] FromBase62String(string s)
    {
        if (s == null) throw new ArgumentNullException("s");
        if (s.Length == 0) return new byte[0];
        var byteLength = (int)Math.Floor((double)s.Length * Math.Log(62d, 256d));

        var number = new BigInteger(0);
        var base62 = new BigInteger(62);
        for (var i = s.Length - 1; i >= 0; i--)
        {
            var c = s[i];
            number = number * base62 + new BigInteger(FromBase62Char(c));
        }

        // BigIntegerのToByteArray()メソッドだと、
        // 末尾にゼロが続くケースなどで正しいバイト長が得られないため
        // 文字列長から計算したバイト長を元にバイト配列化する
        var bytes = new byte[byteLength];
        var base256 = new BigInteger(256);
        for (var i = 0; i < byteLength; i++)
        {
            BigInteger mod256;
            number = BigInteger.DivRem(number, base256, out mod256);
            bytes[i] = (byte)mod256;
        }
        return bytes;
    }

    static int FromBase62Char(char c)
    {
        if ('A' <= c && c <= 'Z')
        {
            return (int)c - (int)'A';
        }
        else if ('a' <= c && c <= 'z')
        {
            return 26 /*A-Z*/ + (int)c - (int)'a';
        }
        else if ('0' <= c && c <= '9')
        {
            return 26 /*A-Z*/  + 26 /*a-z*/ + (int)c - (int)'0';
        }
        throw new ArgumentOutOfRangeException("c");
    }
}