Best Practice : Schema design for Large Number of rows with few columns
I would just go with a bigint with Identity column. Just remember to start it at the negative seed value since sql server does not support unsigned ints. Something like this... 

CREATE TABLE Records
(
 RecordID bigint IDENTITY(-9,223,372,036,854,775,808,1),
 RowLabel varchar(255) NOT NULL,
 CatLabelID INT,
 StartPosition varchar(255),
 EndPosition varchar(255)
)