Okay, I think I finally understand. So, NMinimize expects an expression that represents a function to be minimized. So you need that first argument to look like a function. Using things like Count will just perform the function, but we need an expression for the function. I'm not sure the best way to do this, but one way would be with UnitStep. So, for a 2x2 matrix and using m as our formal symbol, we want something like this:
NMinimize[
{UnitStep[-1/4 + m[1, 1]] + UnitStep[-1/4 + m[1, 2]] + UnitStep[-1/4 + m[2, 1]] + UnitStep[-1/4 + m[2, 2]],
{-1 <= m[1, 1] <= 1, -1 <= m[1, 2] <= 1, -1 <= m[2, 1] <= 1, -1 <= m[2, 2] <= 1}},
{m[1, 1], m[1, 2], m[2, 1], m[2, 2]}]
which evaluates to
{0., {m[1, 1] -> -0.782122, m[1, 2] -> -0.00737865, m[2, 1] -> -0.0810299, m[2, 2] -> -0.624118}}
We need a way to create this data programmatically, so here's one way. I assume you still want to create each matrix separately.
countLargeFn[matrix_?MatrixQ, thresholdFn_] :=
With[
{elems = Flatten[matrix], threshold = thresholdFn[matrix]},
{vars = Select[elems, Not@*NumericQ]},
{Total[UnitStep[elems - threshold]], -1 <= # <= 1 & /@ vars, vars}]
Use it this way:
countLargeFn[Array[m, {2, 2}], 1/Times @@ Dimensions[#] &]
which produces:
{UnitStep[-1/4 + m[1, 1]] + UnitStep[-1/4 + m[1, 2]] + UnitStep[-1/4 + m[2, 1]] + UnitStep[-1/4 + m[2, 2]],
{-1 <= m[1, 1] <= 1, -1 <= m[1, 2] <= 1, -1 <= m[2, 1] <= 1, -1 <= m[2, 2] <= 1},
{m[1, 1], m[1, 2], m[2, 1], m[2, 2]}}
You'd then need to apply this to several symbolic matrices and then aggregate the bits together. All of the unit step expressions and the constraints go in the first argument to NMinimize and then all the variables go into the second argument.
Unfortunately, I must leave the house now and won't look at this again until I get back. I threw that together quickly, and I know it doesn't finish the job for you in its current form. If you can't figure it out, just ask more questions and I'll be back on line in 8 hours or so.