More generally, in case your data is not sorted like this (by lon and then by lat) and you want subdiv to include all levels of lot and lan, you could:

    CPUE <- data.frame(lon = as.vector(replicate(4, sample(13.5:22.5, 10, T))),
                       lat = as.vector(replicate(4, sample(seq(54, 56.25, 0.25), 10, T))))

    num <- findInterval(CPUE$lon, sort(unique(CPUE$lon)))
    lett <- findInterval(CPUE$lat, sort(unique(CPUE$lat)))

    CPUE$subdiv <- paste(num, LETTERS[lett], sep = "")

    CPUE
        lon   lat subdiv
    1  13.5 54.50     1C #this is the first possible "lon" and the third possible "lat"
    2  15.5 54.50     3C
    3  20.5 55.25     8F #this is the eigth possible "lon" and the sixth possible "lat"
    4  19.5 54.00     7A
    5  16.5 55.75     4H

NOTE: This approach won't work if (1) you don't want to include all possible levels of "lon" and "lat", and (2) your data is not sorted as posted.

EDIT

Maybe something like this?:

    CPUE <- data.frame(lon = sort(rep(13.5:22.5, 13)),
                       lat = rep(seq(54.25, 60.25, 0.5), 10))

    lat_names <- findInterval(CPUE$lat, sort(unique(CPUE$lat))) + 36

    lon_names <- as.vector(sapply(LETTERS, paste, 0:9, sep = ""))
    lon_names <- lon_names[match("G3", lon_names):length(lon_names)]
    lon_names <- lon_names[findInterval(CPUE$lon, sort(unique(CPUE$lon)))]

    CPUE$subdiv <- paste(lat_names, lon_names, sep = "")

    > CPUE
         lon   lat subdiv
    1   13.5 54.25   37G3
    2   13.5 54.75   38G3
    3   13.5 55.25   39G3
    4   13.5 55.75   40G3
    5   13.5 56.25   41G3
    6   13.5 56.75   42G3
    7   13.5 57.25   43G3
    8   13.5 57.75   44G3
    9   13.5 58.25   45G3
    10  13.5 58.75   46G3
    11  13.5 59.25   47G3
    12  13.5 59.75   48G3
    13  13.5 60.25   49G3
    14  14.5 54.25   37G4
    15  14.5 54.75   38G4
    16  14.5 55.25   39G4
    17  14.5 55.75   40G4
    18  14.5 56.25   41G4
    19  14.5 56.75   42G4
    20  14.5 57.25   43G4
    ....