First, you don't need to use GetAll: UIDs are assigned by an IMAP server in ascending order, which means you can find the highest uids in your list and ask for a range:
List<long> uids = imap.Search().Where(
Second, page the results as you would in any other case: You're looking for the Skip and Take extension methods (Skip moves past the first N elements in the result, returning the remainder; Take returns the first N elements in the result, dropping any remaining elements):
uids.Skip(pageIndex * pageSize).Take(pageSize);
You can use this method to compute total number of pages:
int numberOfPages = (uids.Count / pageSize)
+ (uids.Count % pageSize == 0 ? 0 : 1);
It takes so much time to get email from server.
Are you sure the problem is not inserting to your database one-by-one?