How to eliminate some edges of a lattice to get exactly k paths? We have an $n$ by $n$ lattice. We want to find a way to eliminate some edges, so that there are exactly $k$ paths from $(1,1)$ to $(n,n)$ of length $2n-2$. (this means our paths should be NE).
I don't know what kind of an answer it might have, but I would be ok, if I could find an algorithm to solve the problem.( I can write a program to work using that algorithm).
One thing to note, is that if we merge to square lattices like the picture, to make a larger $n+m$ by $n+m$ lattice, the number of those paths we want would be the product of those paths in the smaller lattices. for example, if there are p ways to get from A to B with minimal lenght, and q ways to go from B to C, then we have p*q to get from A to C. This means if k is prime, the answer cannot be decomposed into two smaller square lattices like the picture. I dunno how this helps though.
 A: It's not always possible to find an answer to this problem: for instance, with $n = 5$,
there are 70 NE-paths in the full lattice from $(1,1)$ to $(5,5)$, and you can remove edges such that there are 66, 68, or 69 paths, but you can't have 67 paths.
We can see this by marking each edge in the lattice by the number of paths that cross that edge.

We can remove one or two paths by deleting the edges in the upper-left or lower-right corners, but any other edge will remove at least 4 paths, so we cannot end up with 67 paths.
Instead of removing edges, we can consider systematically building up paths, and show that we can always have exactly $k$ paths for any $k$ up to $\binom{n+2}{3}$.
We can get up to $n$ paths easily enough this way:
                                            _
        |           |           |          |_|
        |           |          _|          |_|
        |          _|         |_|          |_|
________|   ______|_|   ______|_|    ______|_|
    1          2           3     ...    n

Then, if we look at the number of paths carried by each horizontal edge in the previous column, we see that the topmost edge adds 1 path, the next one adds 2, and so on:

By adding each of these edges in turn, we can have $n+1$ up to $n+(n-1)$ paths; then we can fill in again from the top to have $n + (n-1) + 1$ up to $n + (n-1) + (n-2)$ paths, and so on, until after adding every edge in this column, we have a total of $n + (n-1) + (n-2) + \dotsb + 1 = \binom{n+1}{2}$ paths.
In the column left of that one, adding the topmost edge adds 1 path; the next one adds 3; the next one adds 6; like so:

These are the successive triangular numbers.
It is a little trickier, but you can prove that by taking combinations of these, and possibly removing one path by deleting an edge in the lower-right corner, you can get any number of paths until you have added all of these edges, yielding a total of $\binom{n+2}{3}$ paths.
(In general, the total number of paths in a rectangular segment, with $i$ edges on one side and $j$ edges on the other, including all of its edges, is $\binom{i+j}{i}$.)
To get an algorithm to yield a subset of edges with exactly $k$ paths, the easiest way I can think of goes back to your original approach, that is, removing edges.
A greedy algorithm with backtracking will work. For each edge, determine the number of paths which cross it. Then remove an edge with the largest number of crossing paths which doesn't leave fewer than $k$ paths. Keep going until you have just $k$ paths left. If all remaining edges have too many crossing paths, then replace the last edge removed, and try another one.
There is nothing particularly clever or efficient about this algorithm, but it is guaranteed to find a solution if it exists. (And it is much more efficient than the most brutal of the possible brute force algorithms, i.e. checking every possible subset of the edges, which would probably take a decade to compute even for $n = 6$.)
Here is an implementation in Python (written for Python 2.7.)
In order to compute the number of crossing paths of an edge, it keeps track of the number of routes from each vertex to all of the vertices northeast of it.
The number of crossing paths of an edge from $(i,j)$ to $(k,l)$ is the number of routes from $(1,1)$ to $(i,j)$, times the number of routes from $(k,l)$ to $(n,n)$.
When this edge is deleted, the number of routes changes from each vertex southwest of $(i,j)$ to each vertex northeast of $(k,l)$.
Specifically, the number of routes no longer available from a vertex $v$ southwest of $(i,j)$, to a vertex $w$ northeast of $(k,l)$, is (the number of routes from $v$ to $(i,j)$) times (the number of routes from $(k,l)$ to $w$).
For convenience of implementation, the vertex indices go from $(0,0)$ to $(n-1,n-1)$ rather than from $(1,1)$ to $(n,n)$.
import numpy as np
from scipy.misc import comb

class LatticePaths(object):
    def __init__(self, N):
        self.N = N
        pathct = np.vectorize(lambda i, j : comb(i+j, i, exact=True), otypes=[object])
        self.verts = [[pathct(*np.indices((N-r,N-c))) for c in range(N)] for r in range(N)]
        self.edges = [e for i in range(N) for j in range(N-1)
                        for e in [((i,j),(i,j+1)), ((j,i),(j+1,i))]]

    def npaths(self, edge):
        '''Number of paths crossing "edge", which is given as a pair of pairs
        ((i,j), (i+1,j)) or ((i,j), (i,j+1)). It is not checked if edge is really an edge.'''
        tor, toc = edge[1]
        return self.verts[0][0][edge[0]] * self.verts[tor][toc][-1,-1]

    def totpaths(self):
        '''The total number of paths from (0,0) to (N-1,N-1) in the lattice.'''
        return self.verts[0][0][-1,-1]

    def deledge(self, killedge):
        '''Remove the given edge from the lattice, updating the number of paths
        between each pair of vertices.'''
        self.edges.remove(killedge)
        (fror,froc), (tor,toc) = killedge
        #iterate over vertices 'below' killedge.from:
        for r in range(fror + 1):
            for c in range(froc + 1):
                self.verts[r][c][tor-r:,toc-c:] -= self.verts[r][c][fror-r,froc-c]*self.verts[tor][toc]

    def restore(self, edge):
        self.edges.append(edge)
        (fror,froc), (tor,toc) = edge
        for r in range(fror + 1):
            for c in range(froc + 1):
                self.verts[r][c][tor-r:,toc-c:] += self.verts[r][c][fror-r,froc-c]*self.verts[tor][toc]

    def __str__(self):
        s = ''
        for r in reversed(range(self.N)):
            for c in range(self.N):
                s += '|' if ((r,c),(r+1,c)) in self.edges and self.npaths(((r,c),(r+1,c))) else ' '
                s += '_' if ((r,c),(r,c+1)) in self.edges and self.npaths(((r,c),(r,c+1))) else ' '
            s += '\n'
        return s

def findpaths(N, K):
    '''Find a subset of the edges in the integer lattice from (0,0) to (N-1,N-1)
    so that there are a total of K distinct NE paths from (0,0) to (N-1,N-1).'''
    LP = LatticePaths(N)
    nRemove = LP.totpaths() - K 
    delsum = 0
    backstack = []
    while delsum < nRemove:
        edglst = sorted((e for e in LP.edges if 1 <= LP.npaths(e) <= nRemove - delsum), key=LP.npaths)
        while backstack and not edglst:
# edglst is empty; there are no suitable edges; backtrack
            #print "BACKTRACKING"
            edglst = backstack.pop()
            delsum -= LP.npaths(edglst[-1])
            LP.restore(edglst.pop())
        if not edglst: # backtracked to beginning
            break
        np = LP.npaths(edglst[-1])
        #print "Chose", np, "edge"
        backstack.append(edglst)
        LP.deledge(edglst[-1])
        delsum += np
    if delsum == nRemove:
        print LP
    else:
        print "No solution"

Here is the output for all the possible numbers $k$ when $n = 4$.
           _ _ _    _ _ _      _ _    _ _ _        _        _  
          |        |_|       _|      |_|       _ _|     _ _|   
          |        |        |_|      |_|      |_|_|    |_|_|   
          |        |        |_|      |_|      |_|      |_|_|   
    0        1        2        3        4        5        6    
  _ _ _    _ _ _      _ _    _ _ _    _ _ _    _ _ _    _ _ _  
 |_|_|    | |_|     _|_|    |_|_|    |_|_ _|  |_|_ _|  |_|_ _| 
 |_|      |_|_|    |_|_|    |_|_|    |_|_ _|  |_|_|_|  |_|_|_| 
 |_|      |_|_|    |_|_|    |_|_|    |_|_|_|  |_|_ _|  |_|_|   
    7        8        9        10       11       12       13   
  _ _ _      _ _    _ _ _    _ _ _      _ _    _ _ _    _ _ _  
 |_|_ _|   _|_|_|  |_|_|_|  |_|_|_|   _|_|_|  |_|_|_|  |_|_|_| 
 |_|_|_|  |_|_|    |_|_|    |_|_|_|  |_|_|_|  |_|_|_|  |_|_|_| 
 |_|_|_|  |_|_|    |_|_|    |_|_ _|  |_|_|    |_|_|    |_|_|_| 
    14       15       16       17       18       19       20   

It works reasonably quickly for inputs up to about $n = 60$, on my computer.
Addendum on Triangular Numbers
Above, we had a collection of edges such that adding the $i$th one created $T_i$ many paths, where $T_i$ is the $i$th triangular number, and we claimed that by adding various combinations of these, and possibly removing one path (by deleting an unrelated edge), we could get any number from 1 up to the sum of all the edges, $\sum_{i=1}^h T_i$.
We can prove this by induction. 
First we need a couple of facts about the triangular numbers:
Lemma 1. After the third triangular number $T_3 = 6$, we can say $i + 1 < T_i$,
by induction (the index $i$ grows by one each time, while $T_i$ grows by $i$ each time.)
Lemma 2. After the fourth triangular number $T_4 = 10$, $T_m$ is always smaller than
the sum of the smaller triangular numbers.
This follows from induction:
if $T_{m-1} \leq \sum_{i=1}^{m-2} T_i$,
then $T_m = T_{m-1} + m$ is less than $\sum_{i=1}^{m-1} T_i$, since $m < T_{m-1}$ (by Lemma 1.)
To prove the claim, we can show how to do the small cases:
$$
\begin{array}{rcccccccccc}
\text{number} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
\text{combo} & 1 & 3 - 1 & 3 & 1 + 3 & 6 - 1 & 6 & 1 + 6 & 3 + 6 - 1 & 3 + 6 & 1 + 3 + 6
\end{array}
$$
Now suppose that for some $m \geq 3$ we can write any number from 1 up to $\sum_{i=1}^m T_i$ in this way.
Then, by adding $T_{m+1}$ to each such combination, we can get each number from $T_{m+1} + 1$
up to $T_{m+1} + \sum_{i=1}^m T_i$.
Since by Lemma 2, $T_{m+1} \leq \sum_{i=1}^m T_i$,
these two sets yield every number from 1 up to $\sum_{i=1}^{m+1} T_i$, as claimed.
