this work, we study the r-circulant matrix C-r = Circ(r)(c(0), c(1), c(2), ..., c(n-1)) such that the entries of C-r are c(i) = M(k,a+ib )or ci = R-k,R-a+ib, where M-k,M-a+ib and R-k,R-a+ib are k-Mersenne and k-Mersenne-Lucas numbers, respectively. We obtain the eigenvalues and determinants for the matrices and some important identities for the k-Mersenne and k-Mersenne-Lucas numbers. Furthermore, we find norms and bounds estimation for the spectral norm for these r-circulant matrices.